Permutations

Difficulty: Medium Source: NeetCode

Problem

Given an array nums of distinct integers, return all the possible permutations. You can 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 = [0, 1] Output: [[0,1],[1,0]]

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

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• Subsets — at each step you’re choosing which element to place next
• Backtracking — making a choice, recursing, then undoing the choice to try another

1. Backtracking with used Array

Intuition

Build the permutation position by position. At each step, scan through all elements and place any element that hasn’t been used yet. After filling a position, mark it as used and recurse to fill the next position. When all positions are filled, record the permutation. Then unmark the element (backtrack) and try the next candidate for this position.

Algorithm

1. Initialize used = [False] * len(nums) and current = [].
2. Define backtrack().
3. If len(current) == len(nums): append a copy to results and return.
4. For each index i in nums:
   • If used[i]: skip.
   • Mark used[i] = True, append nums[i].
   • Recurse.
   • Mark used[i] = False, pop nums[i].

Solution

def permute_used(nums):
    result = []
    used = [False] * len(nums)

    def backtrack(current):
        if len(current) == len(nums):
            result.append(list(current))
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            current.append(nums[i])
            backtrack(current)
            current.pop()
            used[i] = False

    backtrack([])
    return result


print(permute_used([1, 2, 3]))
# [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
print(permute_used([0, 1]))
# [[0,1],[1,0]]

Complexity

• Time: O(n! * n) — n! permutations, each costs O(n) to copy
• Space: O(n) — recursion depth plus the used array

2. Swap-Based Backtracking

Intuition

Think of it differently: the permutation is being built left to right, and at position start we’re deciding which element occupies that slot. We swap nums[start] with each nums[i] (for i >= start), then recurse on the rest of the array (start + 1). After the recursive call, we swap back to restore the original order. This approach modifies nums in place and avoids a separate used array.

Algorithm

1. Define backtrack(start).
2. If start == len(nums): append a copy of nums to results and return.
3. For i from start to len(nums) - 1:
   • Swap nums[start] and nums[i].
   • Recurse with start + 1.
   • Swap nums[start] and nums[i] back.

Solution

def permute(nums):
    result = []

    def backtrack(start):
        if start == len(nums):
            result.append(list(nums))
            return
        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]  # choose
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]  # undo

    backtrack(0)
    return result


print(permute([1, 2, 3]))
# [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
print(permute([0, 1]))
# [[0,1],[1,0]]
print(permute([1]))
# [[1]]

Complexity

• Time: O(n! * n) — n! permutations, each costs O(n) to copy
• Space: O(n) — recursion depth; no extra used array needed

Common Pitfalls

Forgetting to swap back after recursing. In the swap-based approach, if you don’t swap back, the array is permanently modified and subsequent iterations of the loop see a wrong array state.

Appending nums instead of list(nums). At the base case, nums is the live array that keeps changing. You must snapshot it with list(nums) or nums[:].

Confusing permutations with combinations. In permutations, order matters — [1,2,3] and [3,2,1] are different outputs. In combinations (subsets), order doesn’t matter. The used array approach lets every element appear at every position, which is what creates the ordering freedom.