46. Permutations - Explanation

Description

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

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 = [7]

Output: [[7]]

Constraints:

1 <= nums.length <= 6
-10 <= nums[i] <= 10

Recommended Time & Space Complexity

You should aim for a solution with O(n * n!) time and O(n) space, where n is the size of the input array.

Hint 1

A permutation is the same as the array but with the numbers arranged in a different order. The given array itself is also considered a permutation. This means we should make a decision at each step to take any element from the array that has not been chosen previously. By doing this recursively, we can generate all permutations. How do you implement it?

Hint 2

We can use backtracking to explore all possible permutation paths. We initialize a temporary list to append the chosen elements and a boolean array of size n (the same size as the input array) to track which elements have been picked so far (true means the element is chosen; otherwise, false). At each step of recursion, we iterate through the entire array, picking elements that have not been chosen previously, and proceed further along that path. Can you think of the base condition to terminate the current recursive path?

Hint 3

We observe that every permutation has the same size as the input array. Therefore, we can append a copy of the list of chosen elements in the current path to the result list if the size of the list equals the size of the input array terminating the current recursive path.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Recursion

Intuition

The idea is to generate permutations by building them from smaller permutations.

If the list is empty → the only permutation is [].
Otherwise:
1. Take the first number of the list.
2. Recursively get all permutations of the remaining numbers.
3. For each smaller permutation, insert the first number into every possible position.
  - Example:
    If smaller permutation = [2,3] and new number = 1,
    we create: [1,2,3], [2,1,3], [2,3,1].

This works because inserting the new number in all positions ensures we build all unique permutations.

Algorithm

If nums is empty → return [[]].
Recursively call permute(nums[1:]) to get permutations of the smaller list.
For each permutation:
- Insert nums[0] at every position:
  - From index 0 to len(permutation)
- Add each new list to the result.
Return the final result containing all permutations.

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        if len(nums) == 0:
            return [[]]

        perms = self.permute(nums[1:])
        res = []
        for p in perms:
            for i in range(len(p) + 1):
                p_copy = p.copy()
                p_copy.insert(i, nums[0])
                res.append(p_copy)
        return res

Time & Space Complexity

Time complexity: $O(n! * n ^ 2)$
Space complexity: $O(n! * n)$ for the output list.

2. Iteration

Intuition

We build permutations step-by-step using iteration instead of recursion.

Start with one empty permutation: [].

For each number in nums, we take all existing permutations and insert the new number into every possible position.

Example building process for [1,2,3]:

Start: []
Insert 1 → [1]
Insert 2 into every position of [1] → [2,1], [1,2]
Insert 3 into every position of each permutation:
- For [2,1] → [3,2,1], [2,3,1], [2,1,3]
- For [1,2] → [3,1,2], [1,3,2], [1,2,3]

By inserting each number in all positions of all existing permutations, we generate all possible permutations.

Algorithm

Start with perms = [[]].
For each number num in nums:
- Create a new list new_perms.
- For every permutation p in perms:
  - Insert num into every index 0..len(p) to create new permutations.
  - Add each new permutation to new_perms.
- Replace perms with new_perms.
Return perms as the final list of all permutations.

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        perms = [[]]
        for num in nums:
            new_perms = []
            for p in perms:
                for i in range(len(p) + 1):
                    p_copy = p.copy()
                    p_copy.insert(i, num)
                    new_perms.append(p_copy)
            perms = new_perms
        return perms

Time & Space Complexity

Time complexity: $O(n! * n ^ 2)$
Space complexity: $O(n! * n)$ for the output list.

3. Backtracking

Intuition

Backtracking builds permutations by choosing numbers one-by-one and exploring all possible orders.

At every step:

We pick a number that has not been used yet.
Add it to the current permutation.
Recursively continue building.
When we reach a full permutation (length == len(nums)), we save it.
Then we undo the last choice (backtrack) and try a different number.

We use a pick array to mark which elements are already used, ensuring each number appears only once per permutation.

This method explores a decision tree where each level chooses the next number until all numbers are used.

Algorithm

Maintain:
- perm: the current permutation being built.
- pick[i]: whether nums[i] is already used.
- res: list of all completed permutations.
If len(perm) == len(nums), add a copy to res.
Loop through all indices i:
- If pick[i] is false:
  - Mark pick[i] as true.
  - Add nums[i] to perm.
  - Recurse to build further.
  - Backtrack: remove nums[i] and mark pick[i] as false.
Return res.

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        self.res = []
        self.backtrack([], nums, [False] * len(nums))
        return self.res

    def backtrack(self, perm: List[int], nums: List[int], pick: List[bool]):
        if len(perm) == len(nums):
            self.res.append(perm[:])
            return
        for i in range(len(nums)):
            if not pick[i]:
                perm.append(nums[i])
                pick[i] = True
                self.backtrack(perm, nums, pick)
                perm.pop()
                pick[i] = False

Time & Space Complexity

Time complexity: $O(n! * n)$
Space complexity: $O(n! * n)$ for the output list.

4. Backtracking (Bit Mask)

Intuition

We want to generate all permutations, but instead of using a boolean pick array,
we use a bitmask (mask) to track which elements in nums have been used.

Each bit in mask represents whether an index i is used.
Example with 4 numbers:
- mask = 0101 means indices 0 and 2 are already chosen.
This makes checking usage extremely fast using:
- (mask & (1 << i)) → checks if index i is used.
- (mask | (1 << i)) → marks index i as used for the next recursive call.

We build permutations by trying every unused index at each step until we've chosen all numbers.

Algorithm

Start with:
- empty permutation perm
- mask = 0 meaning nothing is used yet
If perm has length equal to nums, add a copy to the result.
Loop through all indices i in nums:
- If bit i in mask is 0 → number not used:
  - Append nums[i] to perm
  - Recurse with mask updated to mark i as used
  - Backtrack: remove the last element from perm
Continue until all permutations are generated.

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        self.res = []
        self.backtrack([], nums, 0)
        return self.res

    def backtrack(self, perm: List[int], nums: List[int], mask: int):
        if len(perm) == len(nums):
            self.res.append(perm[:])
            return
        for i in range(len(nums)):
            if not (mask & (1 << i)):
                perm.append(nums[i])
                self.backtrack(perm, nums, mask | (1 << i))
                perm.pop()

Time & Space Complexity

Time complexity: $O(n! * n)$
Space complexity: $O(n! * n)$ for the output list.

5. Backtracking (Optimal)

Intuition

This approach generates permutations in-place by swapping elements.

Instead of creating new lists or tracking visited elements, we treat the array as divided into:

Fixed prefix (positions 0 to idx - 1)
Free suffix (positions idx to end)

At each step:

We choose which element should go into position idx.
We do this by swapping every element i ≥ idx with idx.
After placing a number at position idx, we recursively fill the next index.
When recursion returns, we swap back to restore the original list (backtracking).

This gives all permutations efficiently and uses O(1) extra space (besides recursion).

Algorithm

Start backtracking from idx = 0.
If idx == len(nums), we have a full permutation → append a copy to result.
For each index i from idx to end:
- Swap nums[idx] and nums[i]
  (placing nums[i] in the current position)
- Recurse with idx + 1
- Swap back to restore original order (backtracking)
Continue until all permutations are generated.

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        self.res = []
        self.backtrack(nums, 0)
        return self.res

    def backtrack(self, nums: List[int], idx: int):
        if idx == len(nums):
            self.res.append(nums[:])
            return
        for i in range(idx, len(nums)):
            nums[idx], nums[i] = nums[i], nums[idx]
            self.backtrack(nums, idx + 1)
            nums[idx], nums[i] = nums[i], nums[idx]

Time & Space Complexity

Time complexity: $O(n! * n)$
Space complexity: $O(n! * n)$ for the output list.

Common Pitfalls

Adding Reference Instead of Copy

When a complete permutation is found, you must add a copy of the current permutation list to the result. Adding the reference directly means all entries in the result will point to the same list, which gets modified during backtracking. Always use perm.copy(), new ArrayList<>(perm), or equivalent.

Forgetting to Backtrack

After recursively exploring with an element added to the permutation, you must remove it (backtrack) before trying the next element. Forgetting to pop the element or reset the visited flag results in incomplete exploration of the decision tree and missing permutations.

Inefficient Element Tracking

Using linear search to check if an element is already in the permutation leads to O(n) overhead per check, resulting in O(n! * n^2) time complexity. Using a boolean visited array or bitmask reduces this to O(1) per check, achieving the optimal O(n! * n) complexity.