Backtracking: subsets and permutations

When you need every answer

Some questions ask for all possibilities: every team you can form from five players, every order in which a delivery rider can visit four addresses, every way to fill a timetable. There is no shortcut to list them all; you must generate them. Backtracking is the clean, standard way to do it with recursion, without missing any and without listing any twice.

Choose, explore, un-choose

Keep a path: the choices made so far (a list). At each step, loop over the options that are still allowed. For each one: choose it (append it to the path), explore (call the function recursively to make the remaining choices), and un-choose it (pop it from the path) so the next option starts from the same state. When the path is complete, save a COPY of it. The undo step is what gives backtracking its name: you walk back up the tree and try another branch.

The decision tree

Draw every state of the path as a node. The empty path is the root; each choice is an edge to a child. For subsets of [1, 2, 3], each level decides one number: take it or skip it. That gives 2 × 2 × 2 = 8 leaves, one per subset. Backtracking is simply a depth-first walk over this tree, which is why the stack depth is only n.

                 []
          take 1/      \skip 1
           [1]            []
        take 2/ \skip   take 2/ \skip
      [1,2]    [1]      [2]     []
       / \     / \      / \     / \
 [1,2,3][1,2][1,3][1] [2,3][2] [3] []

All subsets: 2ⁿ of them

A common way to write it: at each call, the current path is itself a subset, so save a copy; then try adding each later number, starting from index start so that every subset is built in one order only ([1, 2], never [2, 1] as well).

def subsets(nums):
    result, path = [], []

    def backtrack(start):
        result.append(path[:])            # save a COPY of the current subset
        for i in range(start, len(nums)):
            path.append(nums[i])          # choose
            backtrack(i + 1)              # explore
            path.pop()                    # un-choose

    backtrack(0)
    return result

print(subsets([1, 2, 3]))
# Output: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

All permutations: n! of them

A permutation is an ordering of all the items. The first position has n choices, the next n − 1, and so on: n × (n − 1) × … × 1 = n! orderings. Keep a used list of booleans; at each level try every unused item.

def permutations(nums):
    result, path = [], []
    used = [False] * len(nums)

    def backtrack():
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True; path.append(nums[i])     # choose
            backtrack()                              # explore
            path.pop(); used[i] = False              # un-choose

    backtrack()
    return result

print(permutations([1, 2, 3]))
# Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Handling duplicates: sort, then skip

With nums = [1, 2, 2], the code above makes the subset [2] twice, once with each 2. The fix: sort nums first so equal values sit together, and inside the loop skip nums[i] when i > start and nums[i] == nums[i − 1]. In words: at one level of the tree, use each distinct value only once as the next choice. Going deeper (i + 1) can still take the second 2, so [2, 2] is still made, exactly once. Permutations with duplicates use the same idea: skip nums[i] if it equals nums[i − 1] and nums[i − 1] is not currently used.

How big can n be?

Python manages roughly 10⁶ to 10⁷ simple steps per second, so subsets are fine up to about n = 20 and permutations up to about n = 9 or 10. When an interview problem says n ≤ 15 or n ≤ 20, it is often hinting at backtracking. Python's itertools.combinations and itertools.permutations generate these too, but interviewers usually want to see you write the backtracking.

Common mistakes

• Saving the path itself (result.append(path)) instead of a copy: every saved entry is the same list, which ends up empty. Fix: result.append(path[:]) or list(path).
• Forgetting to un-choose (pop, or reset used[i]), so choices leak into the next branch. Fix: every append before the recursive call needs a pop after it.
• Starting the subset loop at 0 instead of start, which creates [1, 2] and [2, 1] as different subsets. Fix: pass i + 1 down.
• Skipping duplicates without sorting first, or with i > 0 instead of i > start, which wrongly drops [2, 2]. Fix: sort, then use i > start.
• Running backtracking on n = 30 and waiting forever. Fix: check 2ⁿ or n! against the limits before you start.