Backtracking

Backtracking explores the tree of partial solutions: make a choice, recurse to extend it, then undo the choice and try the next. With a feasibility check it prunes whole branches that cannot lead to a solution, which is what makes an otherwise exponential search practical. It is the natural way to enumerate subsets, permutations, and combinations, and to solve constraint puzzles like N-queens and Sudoku.

Choose, explore, un-choose

The skeleton is three steps: add the next candidate to the current path, recurse, then remove it. That last step, the un-choose, is the one people forget, and it is essential: it restores the shared state so the next sibling branch starts clean, which is why the same path list can be reused throughout instead of copying it at every node.

Subsets, permutations, and avoiding duplicates

For subsets, passing a start index into the recursion and only choosing elements at or after it prevents generating the same set in a different order, so each subset appears once. Permutations instead need every element available at each position, so they track a used array rather than a start index. The structural difference, start index versus used set, is exactly the difference between combinations and orderings.

Pruning is the real power

Naive enumeration is hopeless for anything but tiny inputs; the payoff comes from rejecting partial solutions as early as possible. In N-queens you check the column and both diagonals before placing a queen, in Sudoku you verify the row, column, and box, and an invalid prefix cuts off an entire subtree. Good pruning is the difference between a search that finishes instantly and one that never returns.

Step by step

1. Choose: add the next candidate element to the current path.
2. Explore: recurse to extend the path.
3. Un-choose: remove the element and try the next option.
4. Prune: skip any choice that already violates a constraint.

def subsets(nums):
    res = []
    def bt(start, path):
        res.append(path[:])                  # every prefix is a valid subset
        for i in range(start, len(nums)):
            path.append(nums[i])
            bt(i + 1, path)                  # start = i+1 avoids duplicates
            path.pop()                       # un-choose
    bt(0, [])
    return res

def permutations(nums):
    res = []
    def bt(path, used):
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True; path.append(nums[i])
            bt(path, used)
            path.pop(); used[i] = False
    bt([], [False] * len(nums))
    return res

Complexity (time and space)

Exponential in general: subsets produce $2^n$ results and permutations $n!$, and any algorithm that lists them must pay that, so the output size is the floor. The extra working space is the recursion depth, $O(n)$. Pruning does not change the worst case but is what makes typical constrained instances finish.

Worked example

All subsets of three elements, in start-index order, and the count of permutations:

print(subsets([1, 2, 3]))
# [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
print(len(permutations([1, 2, 3])))   # 6

Follow-up questions

• Why is the un-choose step necessary? It restores the shared path so the next branch explores from the correct state; without it, choices leak across siblings.
• How does the start index avoid duplicate subsets? Only choosing elements at or after the current index fixes one ordering per set, so each subset is generated exactly once.
• What does pruning buy you? It discards entire subtrees whose prefix already violates a constraint, often turning an intractable search into a fast one.
• Why is backtracking exponential? The solution space itself is exponential ($2^n$ subsets, $n!$ permutations); enumeration cannot be cheaper.
• Backtracking vs dynamic programming? Backtracking enumerates or searches a tree of choices with pruning; DP reuses overlapping subproblem answers, which backtracking does not.

References

1. Skiena, The Algorithm Design Manual (3rd ed.).
2. Knuth, The Art of Computer Programming, Vol. 4A: Combinatorial Algorithms.
3. Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms (CLRS, 4th ed.).