Recursion and Backtracking: Trusting a Smaller Version of the Problem

You’re halfway through the Sudoku in the newspaper. You pencil a 3 into an empty cell — it fits the row, the column, the little box, so far so good. A few cells later you pencil a 7, then a 4, and then you hit a square where every digit from 1 to 9 is already spoken for. Dead end. You don’t crumple the page and start over. You rub out that last pencil mark, try the next digit, and carry on.

That small rhythm — pencil it in, be ready to rub it out — is one of the most powerful problem-solving patterns in all of programming, and it has two halves. Recursion is a function that solves a big problem by trusting itself to solve a smaller one. Backtracking is recursion that makes a guess, explores it, and quietly undoes it when it leads nowhere. By the end of this article you and I will have built both — subsets, permutations, and the N-queens puzzle — and gone deep on the one idea, pruning, that turns a hopeless factorial search into something that finishes in a blink.

Let’s start nowhere near a computer

Forget code. Picture yourself at the entrance of a hedge maze with no map, holding a ball of string. You tie one end to the entrance gate and start walking, unspooling string behind you as you go.

At the first fork you face a choice. You can’t see where either passage leads — but here’s the thing you tell yourself: each passage is just a smaller maze. So you pick one, keep unspooling, and trust that the very same rule will get you through whatever’s down there. If that smaller maze has a fork of its own, you’ll do the exact same thing again. That trust — "a smaller maze is solved the same way as the big one" — is recursion.

Now suppose a passage dead-ends at a hedge wall. You don’t panic and you don’t abandon the maze. You reel the string back in, step by step, until you’re standing at the last fork with an untried passage — and you take it. The string is what makes the reeling-back possible: it’s a perfect record of every step you took, so undoing them is just following it home. That reel-back-and-try-the-next-passage move is backtracking.

Look at what one visit to a fork really involves, because it’s the whole algorithm in three beats:

• Choose — step into a passage, letting out string.
• Explore — solve the smaller maze beyond it (same rule, applied recursively).
• Unchoose — if it dead-ends, reel the string back to the fork, erasing that step, and try the next passage.

And every recursion needs a place to stop: the exit (success) or a hedge wall (failure). That stopping point is the base case. Miss it, and you’d wander the smaller-and-smaller mazes forever.

Where you already meet this

Once you see "solve it by solving a smaller copy, and undo when stuck," it’s hiding all over your day:

• Sudoku and crossword solvers do exactly the pencil-and-eraser dance from the hook.
• Your file manager totalling a folder’s size — a folder’s size is the size of its files plus the size of each subfolder, which is the same question asked on something smaller.
• A GPS rerouting around a closed road backs up to the last junction and tries another way out.
• Your editor matching brackets and colouring nested code parses structure by recursing into each pair of braces.

The most illuminating cousin, though, is the one inside every search box: a regular-expression engine. When you ask a pattern like a(b|c)*d to match some text, the engine is backtracking through choices — at each * it decides "grab another character, or stop?"; at each (b|c) it tries b first, and if the rest of the match fails, it comes back and tries c. A match that dies deep in the string makes it reel all the way back and take the road not chosen, exactly like the maze.

The twist — and the reason it’s worth knowing — is that here the choices multiply. A pattern like (a+)+$ run against aaaaaaaaaaX has an astronomical number of ways to divide those as between the two nested +s, and a naive engine tries them all before admitting the X can never match. This is "catastrophic backtracking," and it has knocked real production services offline. It’s the flip side of the coin we’re about to make shine: backtracking explores a tree of choices, and if that tree is allowed to grow unchecked, it explodes. The entire art is cutting the tree down. Hold that thought.

What it actually looks like

Drop the maze and the regex; let’s look at the shape every backtracking algorithm actually walks. Take the simplest possible job: list every subset of {1, 2, 3} — every way to pick some of the three numbers, from nothing to all of them.

Don’t think of it as a loop. Think of it as a tree of decisions you grow from the empty set, adding one more element at each step:

Every node in that tree is a partial answer — and here’s the key, every node is also a complete, valid subset in its own right. The root is the empty set. Its children add one element; their children add one more; the leaves are the biggest subsets. Backtracking is nothing but a depth-first walk of this tree: go as deep as you can down one branch, record what you find, then back up one level and take the next branch. The whole rest of this article is learning to grow trees like this — and, later, to lop off the branches that can’t bear fruit.

Let’s build one, step by step

We’ll nail plain recursion first, then add the undo that turns it into backtracking, then meet the idea that makes it fast.

Step 1 — recursion: trust the smaller call

Every recursive function has exactly two parts, and every correct one has both:

• a base case — an input so small the answer is immediate, no recursion needed;
• a recursive case — reduce the problem to a smaller version, call yourself, and combine.

Take summing 1 + 2 + … + n. The base case: sumTo(0) is 0. The recursive case: sumTo(n) is n plus whatever sumTo(n - 1) works out to. You don’t loop; you trust the smaller call to be right and add your one piece.

static int sumTo(int n) {
    if (n == 0) {              // base case: the smallest input answers itself
        return 0;
    }
    return n + sumTo(n - 1);   // trust the smaller call, then add my bit
}

Watch the calls actually run and you’ll see the shape that names this whole topic. Each call to sumTo can’t finish until the one inside it finishes, so the calls pile up — "winding down" — until sumTo(0) hits the base case and answers on the spot. Then they resolve in reverse — "unwinding" — each one adding its bit as control returns:

That pile of paused, waiting calls is the call stack, and it’s a real, physical region of your program’s memory. Each waiting sumTo frame holds its own n until the call beneath it returns. The rule to burn in: every recursion needs a base case, and every recursive call must move toward it.

Step 2 — the trap: the base case you never reach

Here’s where recursion bites first. What if the recursive call doesn’t shrink the input?

static int sumTo(int n) {
    if (n == 0) return 0;
    return n + sumTo(n);   // BUG: same n forever → the base case never arrives
}

sumTo(5) calls sumTo(5) calls sumTo(5)… the pile of waiting frames grows without end, and since the call stack is a fixed-size chunk of memory, it fills up and the program dies with a StackOverflowError. The fix is the single character we dropped: recurse on n - 1, not n, so every call is strictly closer to the base case.

There’s a subtler version of the same trap that catches even correct code. A recursion whose depth grows with the input — like sumTo on a few hundred thousand — can overflow the stack even though it’s logically perfect, simply because there isn’t room for that many paused frames (the default stack holds only tens to hundreds of thousands of them). That’s the stack-overflow risk you trade for recursion’s elegance.

Step 3 — backtracking: choose, explore, unchoose

Now the leap. Backtracking is recursion that, at each step, makes a choice, recurses to explore its consequences, and then undoes the choice so it can try the next one. Those three beats — choose, explore, unchoose — are the entire pattern, and you’ll write them for subsets, permutations, N-queens, and a hundred other problems with the same muscle memory.

Watch one frame of the subset search do its job. It’s holding the partial answer [1]. It chooses to add 2, recurses to explore everything that starts with [1, 2], and then — crucially — removes the 2 to get back to exactly [1], so it’s free to try adding 3 next:

In code, the choose / explore / unchoose lines sit right on top of each other, wrapped in a loop over the remaining choices:

private static void buildSubsets(int[] nums, int start,
                                 List<Integer> path, List<List<Integer>> out) {
    out.add(new ArrayList<>(path));           // this node IS a subset — record it
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);                    // choose nums[i]
        buildSubsets(nums, i + 1, path, out); // explore with it chosen
        path.remove(path.size() - 1);         // unchoose — restore the path
    }
}

Two details carry the correctness. We record new ArrayList<>(path) — a copy, because path keeps changing under us. And the start index means each call only considers elements from i onward, so [1, 2] gets built but [2, 1] never does — that’s what keeps subsets from repeating.

Now, the bug that fails this problem. Delete that last line — the path.remove(...) — and everything quietly rots:

path.add(nums[i]);
buildSubsets(nums, i + 1, path, out);
// path.remove(...) deleted → nums[i] never leaves the path

Because path is a single shared list threaded down every branch, forgetting to remove nums[i] means it lingers when control returns to the loop. The next iteration then builds on a polluted path: after finishing [1, 2] you’d fail to shrink back to [1], so instead of trying [1, 3] you’d keep piling onto [1, 2] and emit nonsense. The rule, and it’s the soul of backtracking: whatever you add before recursing, you must remove after. Every choose needs its matching unchoose.

Step 4 — permutations: the same skeleton, a different constraint

Change the question slightly — list every ordering of {1, 2, 3} instead of every subset — and the skeleton doesn’t change at all. Only the rules of what you may choose do. A permutation uses every element (so we only stop at full length) and each element once (so we track which are already in the path):

private static void buildPermutations(int[] nums, boolean[] used,
                                      List<Integer> path, List<List<Integer>> out) {
    if (path.size() == nums.length) {
        out.add(new ArrayList<>(path));       // a full-length path is one permutation
        return;                                // ← the base case
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;                 // skip what's already in the path
        used[i] = true;                        // choose: mark i used
        path.add(nums[i]);                     //         and extend the path
        buildPermutations(nums, used, path, out); // explore
        path.remove(path.size() - 1);          // unchoose: trim the path
        used[i] = false;                       //           and free i again
    }
}

Look how the choose/unchoose discipline now spans two pieces of state — the path and the used flags — and both must be undone, in step. Set used[i] = true on the way down, clear it on the way back up. Forget that second undo and later branches would think elements are still taken and silently drop whole permutations. This is the state-restoration discipline, and the more state a choice touches, the more carefully every bit of it has to roll back — which is exactly what makes the hardest backtracking problem in the interview canon tick.

Pruning: turning a factorial search practical

This is the one facet worth slowing all the way down for. Every search so far had to visit its whole tree — there really are 2^n subsets and n! permutations, and you asked for all of them. But most real problems don’t want every arrangement; they want the ones that satisfy a constraint. And that changes everything, because now you can refuse to explore branches that can’t possibly work. That refusal is called pruning, and it’s the line between a search that finishes and one that never does.

Here’s the idea in one picture. As you grow a partial solution, you run a cheap test — "could this partial still lead to a valid answer?" — before you recurse. If the answer is no, you skip the whole subtree. Not one node: the entire pyramid of arrangements hanging beneath it, which can be factorially large:

The classic showcase is N-queens: place N queens on an N×N board so no two share a row, column, or diagonal. We’ll place exactly one queen per row and choose its column — that alone bakes in "no two in a row." The naive move is to fill every row every possible way and then check the finished board. The pruning move is to check each queen against the ones already placed the instant you place it, and back up the moment there’s a conflict:

Watch the left board. Two queens are down, and row 2 has no safe square — every column is attacked by a queen’s column or one of its diagonals. A naive search wouldn’t notice yet; it’d keep trying to fill rows 2 and 3 anyway, spawning thousands of doomed boards. The pruned search sees that row 2 is hopeless, abandons the entire subtree, backs up, and moves the row-1 queen (right board) — which opens a safe square. That early "no legal square" check is the prune.

public static int countNQueens(int n) {
    boolean[] col  = new boolean[n];         // is column c already taken?
    boolean[] diag = new boolean[2 * n - 1]; // ↘ diagonals: r + c is constant
    boolean[] anti = new boolean[2 * n - 1]; // ↙ diagonals: r - c + (n - 1)
    return placeQueens(0, n, col, diag, anti);
}
 
private static int placeQueens(int row, int n,
                               boolean[] col, boolean[] diag, boolean[] anti) {
    if (row == n) {
        return 1;                            // filled every row — one full solution
    }
    int count = 0;
    for (int c = 0; c < n; c++) {
        int d = row + c, a = row - c + n - 1;
        if (col[c] || diag[d] || anti[a]) {
            continue;                        // PRUNE: this square is attacked
        }
        col[c] = diag[d] = anti[a] = true;   // choose — occupy (row, c)
        count += placeQueens(row + 1, n, col, diag, anti); // explore the next row
        col[c] = diag[d] = anti[a] = false;  // unchoose — vacate (row, c)
    }
    return count;
}

Two things make this pruning pay off, and both are easy to get subtly wrong.

First, the test has to be cheap — ideally O(1). We never re-scan the board to look for conflicts. We keep three boolean arrays that answer "is this square attacked?" in constant time. Every square on one ↘ diagonal shares the same row + c; every square on one ↙ diagonal shares the same row - c (shifted by n - 1 to stay non-negative). So a single array index tells us instantly whether a line is occupied. A prune you have to work to compute can cost more than the branches it saves — the whole point is that the viability check is far cheaper than exploring the subtree it kills.

Second — and this is where correctness lives — those three arrays are shared mutable state threaded through every call, so the bookkeeping must be flawless. When you place a queen you set col[c], diag[d], and anti[a] all to true; when you back out you must set all three back to false before trying the next column. Miss one — clear col but forget anti — and a phantom queen haunts a diagonal that’s actually empty. The search would then prune legal branches and undercount, and it would do so silently: right answers on a tiny board, wrong ones as N grows. Backtracking is correct only if, after a branch returns, the world is byte-for-byte what it was before you entered it. Choose forward, restore back, always in matched pairs.

So how much does the prune actually buy? For the 8×8 board, plant a counter and watch:

Read the last row against the others. The pruned search inspects 2,057 partial boards to find all 92 solutions — versus forty thousand for the permutation approach and nearly seventeen million for the brute one. And the gap only widens with N: pruning doesn’t shave a constant factor off a factorial, it changes which boards exist to be visited at all.

Backtracking vs. brute force

The alternative to backtracking is the honest brute force: generate every candidate, then filter for the valid ones. When does building the answer incrementally earn its keep? Let n be the input size.

The space column is the quiet win: all three carry just one path down the tree, so memory is O(depth), never O(all answers). The time column is the loud one. Plain backtracking and brute force both drown when the tree is factorial — but pruning attacks the tree itself, and a constraint tight enough to reject partials early is what collapses an intractable search into a fast one. (An unpruned backtracking walk is perfectly fine when you genuinely want every result — the trie’s autocomplete collect() is exactly that.)

The complete implementation

Everything above, assembled — subsets, permutations, and the pruned N-queens count in one class:

package dev.fiveyear.backtracking;
 
import java.util.ArrayList;
import java.util.List;
 
public final class Backtracking {
 
    private Backtracking() {}
 
    /** Every subset of nums, in depth-first order. O(n · 2^n). */
    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> out = new ArrayList<>();
        buildSubsets(nums, 0, new ArrayList<>(), out);
        return out;
    }
 
    private static void buildSubsets(int[] nums, int start,
                                     List<Integer> path, List<List<Integer>> out) {
        out.add(new ArrayList<>(path));           // every node is a subset — record it
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);                    // choose nums[i]
            buildSubsets(nums, i + 1, path, out); // explore with it chosen
            path.remove(path.size() - 1);         // unchoose — restore the path
        }
    }
 
    /** Every permutation of nums. O(n · n!). */
    public static List<List<Integer>> permutations(int[] nums) {
        List<List<Integer>> out = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        buildPermutations(nums, used, new ArrayList<>(), out);
        return out;
    }
 
    private static void buildPermutations(int[] nums, boolean[] used,
                                          List<Integer> path, List<List<Integer>> out) {
        if (path.size() == nums.length) {
            out.add(new ArrayList<>(path));       // a full-length path is one permutation
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;                          // skip elements already in the path
            }
            used[i] = true;                        // choose
            path.add(nums[i]);
            buildPermutations(nums, used, path, out); // explore
            path.remove(path.size() - 1);          // unchoose...
            used[i] = false;                       // ...and free it again
        }
    }
 
    /** How many ways N queens fit on an N×N board with no two attacking. */
    public static int countNQueens(int n) {
        boolean[] col = new boolean[n];
        boolean[] diag = new boolean[2 * n - 1];   // r + c is constant on a ↘ diagonal
        boolean[] anti = new boolean[2 * n - 1];   // r - c + (n - 1) on a ↙ diagonal
        return placeQueens(0, n, col, diag, anti);
    }
 
    private static int placeQueens(int row, int n,
                                   boolean[] col, boolean[] diag, boolean[] anti) {
        if (row == n) {
            return 1;                              // every row filled — one full solution
        }
        int count = 0;
        for (int c = 0; c < n; c++) {
            int d = row + c;
            int a = row - c + n - 1;
            if (col[c] || diag[d] || anti[a]) {
                continue;                          // PRUNE: this square is attacked
            }
            col[c] = diag[d] = anti[a] = true;     // choose — occupy the square
            count += placeQueens(row + 1, n, col, diag, anti); // explore next row
            col[c] = diag[d] = anti[a] = false;    // unchoose — vacate it
        }
        return count;
    }
}

And here it is producing exactly the outputs the comments claim:

Backtracking.subsets(new int[] {1, 2, 3});
// 8 subsets: [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]
 
Backtracking.permutations(new int[] {1, 2, 3});
// 6 permutations: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]
 
Backtracking.countNQueens(4);   // 2
Backtracking.countNQueens(8);   // 92  — found from just 2,057 visited boards

The interview corner

Backtracking questions are a favourite because the skeleton is tiny and the details — the unchoose, the copy, the prune — are where candidates quietly fail. Walk in ready.

Ask these before you write a line:

• "Do you want every solution, one solution, or just a count?" Every → collect copies into a list; one → return the moment a leaf succeeds and stop; count → sum the successes. It decides your return type and whether you short-circuit.
• "Can the input have duplicates, and should duplicate outputs be collapsed?" If yes, you’ll sort first and skip equal siblings — otherwise you’ll emit the same subset many times.
• "How big is n?" 2^n subsets and n! permutations blow up fast; past n ≈ 20 (subsets) or n ≈ 11 (permutations) the answer set itself is too large to enumerate, which is the signal you need pruning or dynamic programming, not raw generation.

The follow-up ladder — where a strong candidate keeps climbing:

1. "Return just one solution and stop." Thread a boolean back up (or return the solution object): the instant a leaf succeeds, stop exploring its siblings. Short-circuiting is a one-line change that abandons the rest of the tree.
2. "The input has duplicates — no duplicate subsets." Sort first, then inside the loop skip a value equal to its previous sibling: if (i > start && nums[i] == nums[i - 1]) continue;. That prunes duplicate branches at the source instead of de-duping at the end.
3. "Combination sum — numbers that add to a target, reuse allowed." Carry a running total in the state and prune the branch the moment it exceeds the target — a viability check, the exact move as N-queens. Recurse on i rather than i + 1 to permit reuse.
4. "The recursion is too deep and overflows the stack." Convert to an explicit stack (an ArrayDeque of frames) so depth lives in the heap, not the call stack; or, when branches share subproblems, memoize the results and the exponential recursion collapses into dynamic programming.
5. "Generate valid parentheses / search a word in a grid." Same skeleton: choose the next character or grid step, prune illegal partials early (more ) than (; off the grid or already-visited cell), explore, unchoose. Once you see the pattern, these stop being separate problems.

Three mistakes that fail the round:

• Forgetting the unchoose. Add without a matching remove and the shared path / used / board state leaks into sibling branches — right answers on trivial inputs, garbage the moment the tree branches. The single most common backtracking bug.
• Recording a reference instead of a copy. out.add(path) stores the same list you keep mutating, so every entry ends up identical (usually empty) when the walk finishes. Always new ArrayList<>(path).
• A missing or unreachable base case. No base case overflows the stack outright; the sneakier failure is a viability check so aggressive it prunes branches that could have held the answer — a search that’s fast and wrong, which is the worst kind of wrong.

Where to go from here

You now own the core: recursion trusts a smaller call and needs a base case; backtracking is recursion that chooses, explores, and unchooses; and a cheap "still viable?" prune is what turns a factorial search practical. Three natural next stops, each one loosening an assumption:

• Memoization and dynamic programming — when the recursion tree keeps hitting the same subproblem down different branches, cache each result and the exponential collapses to polynomial. Recursion is the skeleton every DP is built on.
• Branch-and-bound — pruning sharpened with a numeric bound: track the best answer so far and cut any partial that provably can’t beat it. It’s how solvers crack the travelling salesman and knapsack.
• Iterative deepening and explicit-stack DFS — recursion’s reach without its stack-overflow risk, plus a way to search trees too deep (or infinite) to recurse into naively.

For the wider interview toolkit, pair this with the flip-point hunt of binary search, the amortized two-pointer sweep of the sliding window, and the merge-and-query speed of union-find.

Next time you rub out a wrong digit in a Sudoku and pencil in the next one, you’ll know exactly what your brain just did: it hit a dead end, reeled the string back to the last real choice, and tried the next passage. Choose, explore, unchoose — all the way to the exit.