Backtracking Pattern

Next up in the pattern run-through: Backtracking. This one always felt more like “structured brute force” to me than a clever trick, and honestly that’s kind of the point.

What the pattern is

Backtracking is DFS over a tree of decisions, with an explicit undo step. At every node you:

1. make a choice (add something to the current path),
2. recurse into the consequences of that choice,
3. undo the choice (“un-choose”) before trying the next option at that level.

That third step is the whole pattern. Without it you’d just be doing plain recursion that only ever explores one branch. The undo is what lets you reuse the same path variable (a stack, a list, whatever) across every branch instead of allocating a fresh copy at each level — you build it up, look at it, then tear it back down to try the sibling option.

It shows up whenever the problem wants “all possible X” — all subsets, all permutations, all combinations, all valid board placements — where the search space branches but a lot of branches can share the same in-progress state.

The problem

LeetCode 78, “Subsets.” Given an array of distinct integers, return every possible subset (the power set), including the empty set and the full array itself. Order of subsets doesn’t matter, order of elements within a subset doesn’t matter, no duplicates.

For [1,2,3] there are 2^3 = 8 subsets:

[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]

Every element is either in a given subset or it isn’t — that binary choice per element is exactly what backtracking (or, as we’ll see, a non-recursive equivalent) is built to enumerate.

Code walkthrough A: the recursive backtracking version

This is Subsets from Subsets78.cs in my Backtracking folder, untouched:

public static IList<IList<int>> Subsets(int[] nums)
{
    var result = new List<IList<int>>();
    var curPath = new Stack<int>();
    void Backtrack(int start)
    {
        result.Add(curPath.ToList());

        for (int i = start; i < nums.Length; i++)
        {
            curPath.Push(nums[i]);
            Backtrack(i + 1);
            curPath.Pop();
        }
    }

    Backtrack(0);

    return result;
}

The first line inside Backtrack is the one that took me a moment to appreciate: every call records the current path before doing anything else. That’s because every prefix built so far — including the empty one on the very first call — is itself a valid subset. There’s no separate “base case check the length” logic, because there’s no fixed length to reach; every node in the recursion tree is a valid answer, not just the leaves.

Then the loop is the classic push → recurse → pop:

• push — try including nums[i] in the path,
• recurse — call Backtrack(i + 1), so the next choice only ever looks forward from i. That’s what stops [1,2] and [2,1] from both showing up as separate subsets — since order doesn’t matter for a subset, we only ever extend to the right.
• pop — undo the choice, so the next iteration of the loop tries the next number starting from a clean curPath again.

curPath is a single mutable Stack<int> shared across the whole recursion. That’s the memory-efficient part of backtracking: instead of passing a new list down at every call, you mutate one and repair it on the way back up. The curPath.ToList() in the record step is a defensive copy — without it, every entry in result would be a reference to the same stack, which gets mutated right out from under you as the recursion continues.

Code walkthrough B: the iterative “cascading” version

Same file, Subsets2, a completely different mental model:

public static IList<IList<int>> Subsets2(int[] nums)
{
    var res = new List<IList<int>>();
    res.Add(new List<int>());

    foreach (var t in nums)
    {
        var size = res.Count;
        for (int j = 0; j < size; j++)
        {
            List<int> subset = new List<int>(res[j]);
            subset.Add(t);
            res.Add(subset);
        }
    }

    return res;
}

Start with just the empty set. For each new number, look at every subset already in the result list, clone it, and append the new number to the clone. Since the result starts at size 1 and doubles every time a number is processed (1 → 2 → 4 → 8 for three numbers), you end up with the same 2^n subsets, in a different order.

The key trick to notice: size is captured before the inner loop starts, so you’re only ever doubling the subsets that existed before this number was considered — you’re not iterating over the new ones you just added in the same pass (that would spiral into an infinite doubling).

Is this “backtracking”? Not really, not in the undo sense — there’s no push/pop, no shared mutable path, no recursion. It’s an incremental build: each step takes the previous answer and grows it. Same output as part A, same underlying binary-choice-per-element idea, but no decision tree being walked and rewound — just a list getting doubled three times.

One more thing sitting in the same folder: Combination Sum (LC 39) is queued up next but isn’t implemented yet, so no code for it here.

Try it

Below is the recursive Subsets method running on [1, 2, 3] — it’s the one that actually shows the push/recurse/pop shape. Step through it or hit play. The path on top is the live stack; the list below fills in as each path gets recorded, flashing green the instant it happens, and an amber ghost box shows whatever just got popped during backtrack.

Blue = current path. Green flash = a subset just recorded. Amber = backtracking (popping the last choice).

Takeaways

• There are 2^n subsets of an n-element set — one for every element being in-or-out — so any correct solution has to produce that many results no matter how it’s structured.
• The recursive version does O(n) work per subset (the ToList() copy), for O(n · 2^n) total; the iterative doubling version pays the same O(n) copy per subset for the same total, it just gets there without a call stack.
• The two solutions are a nice reminder that “backtracking” describes how you search (push, recurse, undo), not the only way to enumerate a search space — when the branching structure is regular enough, like it is here, you can sometimes flatten the recursion into a plain loop.