Permutations

Permutations is the classic introduction to backtracking — the technique of building a solution one choice at a time, then undoing each choice to explore the next. Once you see the "choose, recurse, un-choose" rhythm here, you will recognize it everywhere.

The slow way first

You could try to generate orderings ad hoc — pick a first number, then a second, then a third — but without a system you end up repeating work or missing cases. A naive approach might build every length-3 sequence of {1, 2, 3} (27 of them) and throw away the ones with a repeat. That wastes most of the effort.

The question to ask: as I build one ordering, how do I make sure I only ever use a number that is still available? If I track which numbers are already in my partial ordering, I never generate an invalid sequence in the first place.

The idea: choose, recurse, un-choose

Build a permutation one position at a time. Keep a growing path (the ordering so far) and a used[] mask marking which numbers are already placed. At each level, loop over the numbers; for every unused one: add it to the path and mark it used, recurse to fill the next position, then remove it and unmark it before trying the next number. When the path holds all the numbers, it is a complete permutation — record a copy.

The key insight: that final undo step is what makes it backtracking. After exploring a branch we restore the state exactly as we found it, so the next choice starts from a clean slate.

Walk through it

Step through the animation for nums = [1, 2, 3]. From the root [ ] we pick 1, then 2, then 3 — the path [1, 2, 3] is full, so it is a leaf and we record it. Then we backtrack: pop 3 and unmark it, pop 2 as well, and from [1] try the other unused number 3 instead, reaching [1, 3, 2]. Repeating this for the branches that start with 2 and with 3 yields all 6 permutations.

Pseudocode

result = empty list
used = all False
define backtrack(path):
    if path has all the numbers:
        add a copy of path to result   # complete permutation
        return
    for each index i:
        if used[i]: skip it             # already in the path
        add nums[i] to path, mark used[i] = True
        backtrack(path)                  # fill the next position
        remove nums[i] from path, used[i] = False   # undo
backtrack(empty path)
return result

The Python solution

def permute(nums):
    result = []
    used = [False] * len(nums)
 
    def backtrack(path):
        if len(path) == len(nums):
            result.append(path[:])      # full permutation
            return
        for i in range(len(nums)):
            if used[i]:
                continue                 # skip already-used
            path.append(nums[i])
            used[i] = True
            backtrack(path)
            path.pop()                   # undo
            used[i] = False
 
    backtrack([])
    return result

• result collects finished permutations; used is the boolean mask of which numbers are currently in the path.
• The base case len(path) == len(nums) means the path is full — we append path[:], a copy, because path keeps changing as we backtrack.
• The for loop tries every index; if used[i]: continue skips numbers already placed, so we never reuse one.
• path.append(nums[i]) plus used[i] = True is the choose step; the recursive backtrack(path) fills the next position.
• path.pop() and used[i] = False are the un-choose step — the undo that lets the next iteration explore a different number from the same clean state.

Complexity

There are n! permutations and copying each into the result costs O(n), so any correct solution is at least O(n · n!) — the output itself is that large. The extra working space is O(n) for the recursion depth, the path, and the used mask (the result list is not counted as extra).

When this pattern shows up

Practice