Lesson

Backtracking

Intuition: a maze and a ball of string

Imagine you're in a maze holding a ball of string. At every fork you choose a corridor and go deeper. If you hit a dead end or find the exit, you wind the string back to the fork, which means you undo the choice, and try the next corridor. That way you're guaranteed to cover every path without getting lost.

That's backtracking. The whole technique rests on three steps:

Choose: add an element to the current solution.
Explore: recursively keep solving the problem.
Un-choose: remove the element and return to exactly the state you were in before step 1.

Backtracking is a depth-first search (DFS) over a decision tree that you never build in memory. It "lives" on the recursion stack.

The decision tree for subsets of [1, 2, 3]

For each number there are two options: take it (left branch) or skip it (right branch). Level 1 decides the fate of the 1, level 2 the 2, level 3 the 3. Each leaf is one finished subset.

Left means take the number, right means skip it. 8 leaves = 2³ subsets. Path to [1,3]: take 1, skip 2, take 3

Follow the path to [1,3]. We took 1 and went left. Then we skipped 2 and went right. Then we took 3 and went left again. Once the leaf is recorded in the answer, the recursion climbs back up, and on every step up we remove whatever we added. That's why a single path list can be honestly reused for every branch.

Template

The skeleton is almost always the same:

backtrack(state):
    if the solution is complete → save a COPY, return
    for each valid choice:
        if the choice is clearly bad → skip it (pruning)
        make the choice
        backtrack(new state)
        undo the choice

Let's walk through the template on an example of our own: all binary strings of length n with no two 1s in a row. It also shows pruning. If the last digit is 1, we don't even try a second 1.

def generate(n):
    res, path = [], []

    def backtrack():
        if len(path) == n:              # solution complete
            res.append("".join(path))   # save a copy
            return
        for ch in "01":
            if ch == "1" and path and path[-1] == "1":
                continue                # pruning: two 1s in a row
            path.append(ch)             # choose
            backtrack()                 # explore
            path.pop()                  # un-choose

    backtrack()
    return res

Subsets, permutations, combinations

These are the three classic shapes of exhaustive search. They share the same skeleton and differ in just two things: which choices are available and when a solution is complete.

Problem	Available choices	When to save	How many answers
Subsets	elements from index `start` onward	at every node	2ⁿ
Combinations of k out of n	elements from index `start` onward	when `len(path) == k`	C(n, k)
Permutations	all elements not yet used (a `used` array)	when `len(path) == n`	n!

The key difference comes down to one line:

start means order doesn't matter. We only take elements to the right of the current one, so [1,2] and [2,1] never both show up.
used[] means order matters. You can take any element as long as it isn't already in path.

Pruning

Pruning is a check you make before you go down a branch: "Can this branch even lead to an answer?" If it can't, you skip the whole subtree.

Typical pruning:

A constraint is violated. Like two 1s in a row in our example.
The sum already exceeds the target. If the elements are sorted first, you can break right away, since the numbers only get bigger from there.
Not enough elements left. For combinations: if there are fewer elements left in the array than you still need to reach k, there's no point going on.
Duplicates. After sorting, the check if i > start and nums[i] == nums[i-1]: continue removes repeated branches.

Pruning doesn't change the worst-case complexity, but in practice it can make the search dozens of times faster. Always mention it in an interview.

Complexity

Subsets: O(n · 2ⁿ). There are 2ⁿ answers, and copying each one takes up to n.
Permutations: O(n · n!).
Combinations: O(k · C(n, k)).
Space: O(n) for the recursion depth and path, not counting the answer itself.

That's exponential complexity, and that's fine: that's simply how many answers there are, and you can't list them any faster. Which gives you a practical rule of thumb: if the problem says n ≤ 10–20, that's a hint toward backtracking.

What it sounds like in an interview

"The task is to enumerate every option, so it's backtracking. I build a decision tree: at each step I pick the next element, recurse deeper, then roll back the choice. To avoid duplicates, I pass a start index. I prune branches where the sum is already over the target. The complexity is O(n · 2ⁿ) because there are exponentially many answers, and space is O(n) for the stack."

Common mistakes

Saving path instead of a copy. At the end, every answer turns out to be the same empty list. You need path[:], new ArrayList<>(path), or append([]int(nil), path...) in Go.
Forgetting to undo the choice. Without pop(), path collects junk from neighboring branches.
Mixing up start and used. With used on a subsets problem you'll get extra duplicates, and with start on a permutations problem you'll lose some of the options.
Pruning after the recursive call. You have to check a branch before you enter it.

Remember the rhythm "choose → explore → undo," and almost any exhaustive-search problem becomes a matter of filling in the same template. Next, let's lock it in with practice.