Permutations

How it works

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:

1. We choose which element should go into position idx.
2. We do this by swapping every element i ≥ idx with idx.
3. After placing a number at position idx, we recursively fill the next index.
4. 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).

Steps

1. Start backtracking from idx = 0.
2. If idx == len(nums), we have a full permutation → append a copy to result.
3. 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)
4. Continue until all permutations are generated.

Complexity

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

Things to watch for

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.

from typing import List

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]

class Solution {
    vector<vector<int>> res;
public:
    vector<vector<int>> permute(vector<int>& nums) {
        backtrack(nums, 0);
        return res;
    }

    void backtrack(vector<int>& nums, int idx) {
        if (idx == nums.size()) {
            res.push_back(nums);
            return;
        }
        for (int i = idx; i < nums.size(); i++) {
            swap(nums[idx], nums[i]);
            backtrack(nums, idx + 1);
            swap(nums[idx], nums[i]);
        }
    }
};