Permutations: building every ordering with backtracking

The first time I coded a permutation generator I used Python's itertools.permutations and moved on. Four lines, correct output, done. A week later I hit a variant where I needed to prune the search space mid-recursion, and the library call was useless. That is the real reason to understand how the backtracking version works: not because itertools is wrong, but because it is a black box that breaks the moment the problem changes shape.

LeetCode 46 asks: given an array of distinct integers, return all possible permutations. For [1, 2, 3] the answer is six orderings: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]].

What the constraints force

1 <= nums.length <= 6. Six elements, maximum. The number of permutations of n distinct elements is n!, so at n=6 that is 720 permutations. Every approach you can think of — including the naive ones — runs comfortably inside any time limit here.

-10 <= nums[i] <= 10, all distinct. The distinct constraint is doing the most work: it means you never need deduplication logic. Every element is uniquely identifiable. If there were duplicates you'd be on LeetCode 47, which is the harder problem in this series. Here you can index elements by position without worrying about equal values.

These two constraints together give you permission to use any algorithm that is correct. The question is not "can I make this fast enough?" but "which version teaches me the pattern I can generalize?"

Why a library call is the wrong first move

Python makes it trivial:

from itertools import permutations
 
class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        return [list(p) for p in permutations(nums)]

C# has no direct equivalent — Enumerable doesn't ship a permutation method — so you'd have to implement it manually anyway. But even in Python, I'd argue starting here is counterproductive: itertools.permutations gives you no intuition for the structure of the enumeration. You cannot prune it, you cannot modify the ordering rule, and you cannot explain it in an interview. The output is correct; the understanding is absent.

Time: O(n! _ n) — n! permutations, each requiring O(n) work to copy into the result list. Space: O(n! _ n) for the output, plus O(n) for the internal iterator state. Same asymptotic cost as the explicit approaches.

I include it here because it is a real approach and the source covers it, but I would not ship it if I expected to ever need to modify the logic.

Backtracking: building the decision tree explicitly

The core idea is to think of each permutation as a sequence of choices: pick a first element, then a second from the remaining, then a third from whatever is left, and so on. The structure is a tree where each level corresponds to one position in the permutation.

Each path from root to a leaf is one complete permutation. The algorithm walks this tree in DFS order, building the path as it goes and discarding it when it backtracks.

To avoid choosing the same element twice, you need to track which elements are already in the current path. The cleanest way is a used boolean array indexed by position. At each recursive call, scan all positions; skip any that are already marked. When you add element at index i, set used[i] = True before recursing and used[i] = False after — that is the "undo" step that makes backtracking work.

A subtler version of this approach skips the used array and checks if num in current_permutation instead. That works correctly but costs O(n) per check rather than O(1), so it is strictly slower by a constant factor. With n <= 6 you will never notice the difference, but the used array habit transfers better to larger inputs.

Tracing [1, 2, 3] step by step

call backtrack(), current=[], used=[F,F,F]
  try i=0 (val=1): current=[1], used=[T,F,F]
    try i=1 (val=2): current=[1,2], used=[T,T,F]
      try i=2 (val=3): current=[1,2,3], used=[T,T,T]
        len == 3 → append [1,2,3] to result; return
      undo i=2: current=[1,2], used=[T,T,F]
    undo i=1: current=[1], used=[T,F,F]
    try i=2 (val=3): current=[1,3], used=[T,F,T]
      try i=1 (val=2): current=[1,3,2], used=[T,T,T]
        len == 3 → append [1,3,2] to result; return
      undo i=1: current=[1,3], used=[T,F,T]
    undo i=2: current=[1], used=[T,F,F]
  undo i=0: current=[], used=[F,F,F]
  ... (repeat for i=1, i=2 as first choice)

The undo step is the whole mechanism. Without it the used array accumulates marks and later calls see a permanently contaminated state.

class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        result = []
        n = len(nums)
        used = [False] * n
        current = []
 
        def backtrack():
            if len(current) == n:
                result.append(current[:])
                return
            for i in range(n):
                if used[i]:
                    continue
                used[i] = True
                current.append(nums[i])
                backtrack()
                current.pop()
                used[i] = False
 
        backtrack()
        return result

The current[:] copy on the base case is not optional. current is a single list that the recursion mutates throughout — if you append the list object itself, every entry in result ends up pointing to the same list, which will be empty when the recursion finishes. Copy on collect.

public class Solution {
    public IList<IList<int>> Permute(int[] nums) {
        var result = new List<IList<int>>();
        var current = new List<int>();
        var used = new bool[nums.Length];
 
        void Backtrack() {
            if (current.Count == nums.Length) {
                result.Add(new List<int>(current));
                return;
            }
            for (int i = 0; i < nums.Length; i++) {
                if (used[i]) continue;
                used[i] = true;
                current.Add(nums[i]);
                Backtrack();
                current.RemoveAt(current.Count - 1);
                used[i] = false;
            }
        }
 
        Backtrack();
        return result;
    }
}

Time: O(n! _ n). The number of leaves in the decision tree is n!, and writing each leaf into the result takes O(n). Space: O(n! _ n) for the output plus O(n) for the call stack depth, the used array, and current.

Swap-based backtracking: no auxiliary arrays

There is a tighter version that avoids both the used array and the current list by operating directly on nums. The idea: at each recursive level, the elements to the left of a start index have already been placed. To choose the next element, swap each remaining element into position start, recurse, then swap back.

class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        result = []
 
        def backtrack(start: int):
            if start == len(nums):
                result.append(nums[:])
                return
            for i in range(start, len(nums)):
                nums[start], nums[i] = nums[i], nums[start]
                backtrack(start + 1)
                nums[start], nums[i] = nums[i], nums[start]
 
        backtrack(0)
        return result

public class Solution {
    public IList<IList<int>> Permute(int[] nums) {
        var result = new List<IList<int>>();
 
        void Backtrack(int start) {
            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]);
                Backtrack(start + 1);
                (nums[start], nums[i]) = (nums[i], nums[start]);
            }
        }
 
        Backtrack(0);
        return result;
    }
}

When start == 0 and i == 0, the swap is a no-op (swapping an element with itself), so [1, 2, 3] stays [1, 2, 3] — the first permutation is the original array order. When start == 0 and i == 1, you get [2, 1, 3], then recurse to fix positions 1 and 2 with 2 already placed. The swap-back after the recursive call restores nums to exactly the state it was in before that iteration, which is what makes the loop correct.

This version uses no auxiliary structures beyond the call stack and the output list. In terms of big-O it is the same: O(n! _ n) time, O(n! _ n + n) space. The constant factor is slightly better in practice because there is no used array scan and no current list to maintain.

The tradeoff is readability. The used-array version makes the "pick from remaining" logic explicit and easy to verify. The swap version is compact but the invariant ("elements left of start are already placed") is implicit in the array state, which makes it harder to debug and harder to adapt when you need to add pruning conditions.

Edge cases

Single element, nums = [1]: the base case fires immediately on the first call (len(current) == 1 == n), and [[1]] is returned. All three approaches handle this without special-casing.

Two elements, nums = [0, 1]: produces [[0,1],[1,0]]. Worth checking explicitly because the swap version visits i == start on the first iteration (no-op swap), recurses, then tries i == start+1 (real swap). Both orderings are generated.

Negative values: no code path branches on element values, so nums = [-1, 0, 1] works identically to [1, 2, 3]. The -10 <= nums[i] <= 10 range is irrelevant to the algorithm.

All elements are guaranteed distinct by the problem statement — the used array approach relies on this. If you fed it duplicates, the output would contain duplicate permutations (LeetCode 47 adds a sort + skip step to handle that). The swap approach would produce the same issue.

Comparison

All three are O(n! * n) — this is the information-theoretic lower bound for generating all permutations. You cannot do better; there are n! outputs each of length n.

Which one I'd actually use

For an interview, the visited-array backtracking version. It is the most readable of the three "real" implementations, the invariant is explicit, and it extends directly to pruning-based variants. I can write it from memory in about two minutes and talk through it while coding.

For production code in Python where I just need the output and will never modify the enumeration logic, itertools.permutations is fine. It is tested, fast, and one line.

The swap version I reach for when memory is tight and n is larger — in practice that usually means a different problem family, since n=6 from the constraint here makes the distinction irrelevant.

Where this sits in the backtracking series

This is seriesOrder 3, after Subsets (78) and Combination Sum (39). Subsets introduced the include/exclude branching model where you make a binary decision at each element. Combination Sum introduced target-constrained pruning that cuts branches early. Permutations introduces the visited-set pattern: every element is available at every level, so you need explicit bookkeeping to avoid reuse.

The four closest relatives:

• LeetCode 47 — Permutations II: same shape, but nums may contain duplicates. Adds a sort step and a "skip if same value as previous sibling" condition inside the loop. The used array stays; it gains one extra guard.
• LeetCode 77 — Combinations: pick k elements from [1..n] without order mattering. Uses the backtracking skeleton but iterates from a start index (not the whole array) to avoid counting the same set twice.
• LeetCode 39 — Combination Sum: pick elements that sum to a target; elements can be reused. Adds a pruning condition (remaining < 0 → return) that makes the tree finite even with repetition.
• LeetCode 17 — Letter Combinations of a Phone Number: generate all strings from a multi-level alphabet. The same DFS pattern, but each level iterates over a different set of characters rather than a shared pool.

The underlying mental model across all of them is the same: a decision tree where each node is a partial answer, each edge is one choice, and the algorithm is a DFS that collects complete paths. Permutations is the cleanest version of that model.