Backtracking

First PublishedFeb 11, 2026ByAtif Alam

Difficulty: High. ROI: High.

Other common names: Recursive backtracking, DFS + undo.

When to use: Use when you need to generate all valid configurations (permutations, subsets, placements) or find one that satisfies constraints (e.g. N-Queens, Sudoku). You try a choice, recurse, then undo the choice if it leads to a dead end.

Idea: Build a solution step by step. At each step, try each valid option, recurse, then undo (backtrack) so you can try the next option. Often implemented as DFS with a mutable path or state that you revert after the recursive call.

Time / space: Depends on problem; often exponential in the input size. Space O(depth) for recursion.

Example #1 — All Subsets

Generate all subsets of an array by backtracking: at each step record the current path, then try adding each remaining element, recurse, and undo (pop) so the next choice can be tried.

Sample input and output

1
print(subsets([1, 2]))  # [[], [1], [1, 2], [2]]

Sample input: nums = [1, 2].
Sample output: [[], [1], [1, 2], [2]] — all subsets: empty, 1, 2, 2.

Code (with inline comments)

1
def subsets(nums):
2
    result = []
3
    def backtrack(start, path):
4
        result.append(path[:])   # record current subset (copy so we don't mutate later)
5
        for i in range(start, len(nums)):
6
            path.append(nums[i])
7
            backtrack(i + 1, path)  # only pick from indices ≥ i+1 (no duplicates)
8
            path.pop()              # undo: try next candidate at this position
9
    backtrack(0, [])
10
    return result

Line-by-line:

result = [] — We’ll collect every subset (as a list) here.
def backtrack(start, path): — start is the first index we’re allowed to pick from (so we build subsets in order and avoid duplicates). path is the current subset we’re building.
result.append(path[:]) — path[:] makes a copy of the current path. We append that copy so every subset we found is saved; if we appended path itself, later changes would change the stored subset too.
for i in range(start, len(nums)): — Try each index from start to the end as the next element in the subset.
path.append(nums[i]); backtrack(i + 1, path); path.pop() — Add the element, recurse (only consider indices after i so we don’t reuse or reorder), then backtrack: remove the element so we can try the next choice at this “slot.”

Execution trace (numbered list)

For nums = [1, 2]:

Step 1: backtrack(0, []). Append []. path=[]. i=0: append 1, recurse.
Step 2: backtrack(1, [1]). Append [1]. i=1: append 2, recurse.
Step 3: backtrack(2, [1,2]). Append [1,2]. No i. pop 2.
Step 4: Back in backtrack(1,[1]). pop 1. i=1: append 2, recurse.
Step 5: backtrack(2, [2]). Append [2]. No i. pop 2. Done. result = [[], [1], [1,2], [2]].

Execution trace (code with step comments)

1
# backtrack(0, []) → append [] → i=0: path=[1], backtrack(1,[1])
2
#   backtrack(1,[1]) → append [1] → i=1: path=[1,2], backtrack(2,[1,2])
3
#     backtrack(2,[1,2]) → append [1,2] → pop 2
4
#   pop 1 → i=1: path=[2], backtrack(2,[2])
5
#     backtrack(2,[2]) → append [2] → pop 2
6
# result = [[], [1], [1,2], [2]]

Execution trace (ASCII diagram)

Tree of choices: at each node we record path, then branch on “add next element or not.”

1
        []
2
       /   \
3
    [1]     [2]
4
    /  \
5
[1,2]  (done)
6
result: [], [1], [1,2], [2]