Permutations

Given an array of distinct integers, return all the possible permutations in any order

Language Selection

Choose your preferred programming language

Showing: Python

Permutations

Problem Statement

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Constraints:

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • All the integers of nums are unique

Examples:

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1]
Output: [[1]]

Approach 1: Backtracking with Swap

Algorithm:

  1. Use an index to track the current position being filled
  2. Swap the current index with every index from current to end
  3. Recurse for the next position
  4. Swap back (backtrack) to restore the original order
  5. When the index reaches the end, a complete permutation is formed

Time Complexity: O(n * n!) Space Complexity: O(n * n!)

Python:

def permute(nums):
    """
    Generate all permutations using backtracking with swap
    Time: O(n * n!)
    Space: O(n * n!)
    """
    result = []

    def backtrack(start):
        if start == len(nums):
            result.append(nums[:])  # Add a copy
            return

        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]  # Swap
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]  # Swap back

    backtrack(0)
    return result

Java:

class Solution {
    /**
     * Generate all permutations using backtracking with swap
     * Time: O(n * n!)
     * Space: O(n * n!)
     */
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, result);
        return result;
    }

    private void backtrack(int[] nums, int start, List<List<Integer>> result) {
        if (start == nums.length) {
            List<Integer> perm = new ArrayList<>();
            for (int num : nums) {
                perm.add(num);
            }
            result.add(perm);
            return;
        }

        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i);
            backtrack(nums, start + 1, result);
            swap(nums, start, i);  // Swap back
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Go:

// permute - Generate all permutations using backtracking with swap
// Time: O(n * n!)
// Space: O(n * n!)
func permute(nums []int) [][]int {
    var result [][]int

    var backtrack func(start int)
    backtrack = func(start int) {
        if start == len(nums) {
            perm := make([]int, len(nums))
            copy(perm, nums)
            result = append(result, perm)
            return
        }

        for i := start; i < len(nums); i++ {
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start] // Swap back
        }
    }

    backtrack(0)
    return result
}

JavaScript:

/**
 * Generate all permutations using backtracking with swap
 * Time: O(n * n!)
 * Space: O(n * n!)
 */
function permute(nums) {
    const result = [];

    function backtrack(start) {
        if (start === nums.length) {
            result.push([...nums]);
            return;
        }

        for (let i = start; i < nums.length; i++) {
            [nums[start], nums[i]] = [nums[i], nums[start]];  // Swap
            backtrack(start + 1);
            [nums[start], nums[i]] = [nums[i], nums[start]];  // Swap back
        }
    }

    backtrack(0);
    return result;
}

C#:

public class Solution {
    /// <summary>
    /// Generate all permutations using backtracking with swap
    /// Time: O(n * n!)
    /// Space: O(n * n!)
    /// </summary>
    public IList<IList<int>> Permute(int[] nums) {
        IList<IList<int>> result = new List<IList<int>>();
        Backtrack(nums, 0, result);
        return result;
    }

    private void Backtrack(int[] nums, int start, IList<IList<int>> result) {
        if (start == nums.Length) {
            result.Add(new List<int>(nums));
            return;
        }

        for (int i = start; i < nums.Length; i++) {
            (nums[start], nums[i]) = (nums[i], nums[start]);  // Swap
            Backtrack(nums, start + 1, result);
            (nums[start], nums[i]) = (nums[i], nums[start]);  // Swap back
        }
    }
}

Approach 2: Backtracking with Visited Set

Algorithm:

  1. Maintain a boolean array (or set) to track which elements are currently used
  2. Build the permutation element by element
  3. At each step, try every unused element
  4. When the permutation reaches length n, record it
  5. Mark elements as unused when backtracking

Time Complexity: O(n * n!) Space Complexity: O(n * n!)

Python:

def permute(nums):
    """
    Generate all permutations using backtracking with visited set
    Time: O(n * n!)
    Space: O(n * n!)
    """
    result = []
    used = [False] * len(nums)

    def backtrack(current):
        if len(current) == len(nums):
            result.append(current[:])
            return

        for i in range(len(nums)):
            if not used[i]:
                used[i] = True
                current.append(nums[i])
                backtrack(current)
                current.pop()       # Backtrack
                used[i] = False     # Backtrack

    backtrack([])
    return result

Java:

class Solution {
    /**
     * Generate all permutations using backtracking with visited set
     * Time: O(n * n!)
     * Space: O(n * n!)
     */
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        backtrack(nums, used, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] nums, boolean[] used, List<Integer> current,
                           List<List<Integer>> result) {
        if (current.size() == nums.length) {
            result.add(new ArrayList<>(current));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                used[i] = true;
                current.add(nums[i]);
                backtrack(nums, used, current, result);
                current.remove(current.size() - 1);  // Backtrack
                used[i] = false;                      // Backtrack
            }
        }
    }
}

Go:

// permute - Generate all permutations using backtracking with visited set
// Time: O(n * n!)
// Space: O(n * n!)
func permute(nums []int) [][]int {
    var result [][]int
    used := make([]bool, len(nums))

    var backtrack func(current []int)
    backtrack = func(current []int) {
        if len(current) == len(nums) {
            perm := make([]int, len(current))
            copy(perm, current)
            result = append(result, perm)
            return
        }

        for i := 0; i < len(nums); i++ {
            if !used[i] {
                used[i] = true
                current = append(current, nums[i])
                backtrack(current)
                current = current[:len(current)-1] // Backtrack
                used[i] = false                    // Backtrack
            }
        }
    }

    backtrack([]int{})
    return result
}

JavaScript:

/**
 * Generate all permutations using backtracking with visited set
 * Time: O(n * n!)
 * Space: O(n * n!)
 */
function permute(nums) {
    const result = [];
    const used = new Array(nums.length).fill(false);

    function backtrack(current) {
        if (current.length === nums.length) {
            result.push([...current]);
            return;
        }

        for (let i = 0; i < nums.length; i++) {
            if (!used[i]) {
                used[i] = true;
                current.push(nums[i]);
                backtrack(current);
                current.pop();       // Backtrack
                used[i] = false;     // Backtrack
            }
        }
    }

    backtrack([]);
    return result;
}

C#:

public class Solution {
    /// <summary>
    /// Generate all permutations using backtracking with visited set
    /// Time: O(n * n!)
    /// Space: O(n * n!)
    /// </summary>
    public IList<IList<int>> Permute(int[] nums) {
        IList<IList<int>> result = new List<IList<int>>();
        bool[] used = new bool[nums.Length];
        Backtrack(nums, used, new List<int>(), result);
        return result;
    }

    private void Backtrack(int[] nums, bool[] used, List<int> current,
                           IList<IList<int>> result) {
        if (current.Count == nums.Length) {
            result.Add(new List<int>(current));
            return;
        }

        for (int i = 0; i < nums.Length; i++) {
            if (!used[i]) {
                used[i] = true;
                current.Add(nums[i]);
                Backtrack(nums, used, current, result);
                current.RemoveAt(current.Count - 1);  // Backtrack
                used[i] = false;                       // Backtrack
            }
        }
    }
}

Key Insights

  1. Swap vs Visited: The swap approach modifies the array in-place and avoids extra space for a visited array. The visited approach is more intuitive and easier to extend to problems with duplicates.

  2. Permutation Count: There are exactly n! permutations of n distinct elements. Each permutation has n elements, so the total output size is O(n * n!).

  3. Backtracking Guarantee: By restoring state after each recursive call (swapping back or unmarking visited), we ensure the array returns to its original state for the next iteration.

  4. Decision Tree: The recursion tree has n branches at the first level, n-1 at the second, and so on, producing n! leaf nodes corresponding to the n! permutations.

  5. Distinct Elements: Since all elements are unique, every arrangement is a valid distinct permutation. No duplicate-checking logic is needed.

Edge Cases

  • Single element: [1] returns [[1]]
  • Two elements: [0,1] returns [[0,1],[1,0]]
  • Negative numbers: [-1,0,1] produces all 6 permutations, values do not affect the algorithm
  • Maximum length (6 elements): produces 720 permutations, well within time limits

Test Cases

# Test case 1: Three elements
result = permute([1,2,3])
assert len(result) == 6
assert sorted(result) == sorted([[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]])

# Test case 2: Two elements
result = permute([0,1])
assert sorted(result) == sorted([[0,1],[1,0]])

# Test case 3: Single element
assert permute([1]) == [[1]]

# Test case 4: Negative numbers
result = permute([-1,0,1])
assert len(result) == 6

# Test case 5: Maximum length
result = permute([1,2,3,4,5,6])
assert len(result) == 720  # 6! = 720

Common Mistakes

  1. Forgetting to copy: Appending current directly instead of current[:] or new ArrayList<>(current) means all entries in the result end up as references to the same (eventually empty) list.
  2. Not swapping back: Omitting the reverse swap corrupts the array for subsequent iterations, producing incorrect permutations.
  3. Not resetting visited: Forgetting to set used[i] = false after backtracking means elements are permanently excluded, resulting in incomplete results.
  4. Using a set for dedup when unnecessary: Since elements are distinct, there are no duplicates to filter. Adding dedup logic wastes time.
  5. Confusing permutations with subsets: Permutations use all elements (length n), while subsets can have any length from 0 to n.