Recursion and Backtracking (Java + Kotlin)

Backtracking is exhaustive DFS over the tree of partial candidates: at each node you make one choice, recurse, then undo it — pruning any branch that provably cannot reach a valid or optimal answer. Learn one six-line skeleton and every subsets / permutations / combinations / constraint-placement problem becomes the same code with three blanks filled in.

Series map: 00 playbook · 01 two pointers & sliding window · 02 binary search, stacks & intervals · 03 trees & graphs · 04 recursion & backtracking (this file) · 05 dynamic programming · 06 staff+ practical & OOD. Companion (non-series): data-structures-java-kotlin-study-guide.md — reach there for why a HashMap / ArrayDeque / HashSet behaves as it does (buckets, boxing, cache locality). This guide uses those structures as tools and spends its words on the algorithm.

The mental model#

Backtracking builds a candidate solution one choice at a time, and abandons a partial candidate the instant it can no longer be completed into a valid (or optimal) solution. It is a depth-first walk over the tree of partial solutions: each node is a partial candidate, each edge is one choice, each leaf is a complete candidate. The whole method is three lines repeated at every node — choose → recurse → un-choose.

Two numbers govern everything:

Cost = (number of nodes in the decision tree) × (work per node). You reason about a backtracking solution by drawing its tree and counting nodes as branching^depth. Subsets: 2 choices (in/out) × depth n → 2^n leaves. Permutations: n then n−1 then … → n! leaves. This is why complexity is stated as O(2^n · n), O(n! · n), etc. — the tree size times the per-leaf copy.
Pruning shrinks the tree, not the per-node work. The entire art of making backtracking fast is cutting branches early — before you descend into a subtree that cannot yield a solution. A missing prune doesn't give a wrong answer; it gives a TLE.

Three invariants you will repeat until they are muscle memory:

Every choice must be undone. After recurse returns, the state must be exactly what it was before choose. Skip the undo and state leaks sideways into sibling branches — the single most common backtracking bug.
Record a copy of the partial solution, never the live object. The path is a mutable buffer you keep mutating; if you stash the reference, every result ends up pointing at the same (finally empty) list.
Backtracking enumerates distinct paths; it does not reuse subresults. That is the exact line between backtracking and DP. When the recursion’s paths overlap — the same state is reached many ways — you memoize the return value and it becomes top-down DP (§6, and guide 05). When every path is distinct (subsets, permutations), there is nothing to reuse and memoization buys nothing.

Everything below is that model instantiated. Recursion first (backtracking is a special case of it), then the skeleton, then the problem families, then pruning and the bridge to DP.

1. Recursion fundamentals#

Recognition cue. The problem is defined in terms of smaller versions of itself: a tree/graph (subtree, neighbour), a sequence you peel one element off, a search space that splits. If you can phrase "the answer for n in terms of the answer for < n," recursion is the natural shape.

Every recursion is exactly two things:

a base case — the smallest input, answered directly, no recursive call; and
a recursive case — reduce toward the base case and combine.

The recursive leap of faith. Do not trace the whole call stack in your head. Assume the recursive call already returns the correct answer for the smaller input; your only jobs are (1) get the base case right and (2) combine the sub-answer(s) correctly. Trusting the call is what lets you write fib or a tree recursion in four lines instead of drowning in stack frames.

The call stack. Each call pushes a frame (parameters, locals, return address). Recursion of depth d uses O(d) stack. The JVM does not do tail-call optimization — a tail-recursive Java method of depth 10^6 still overflows. Kotlin’s tailrec modifier rewrites a tail-recursive function into a loop at compile time; use it, or convert to iteration by hand, when depth is unbounded.

Warm-ups (know these cold — they are the vocabulary)#

Factorial and naive Fibonacci. fib is the canonical "why naive recursion is exponential" example — and the motivation for DP (guide 05):

kotlin

fun factorial(n: Int): Long = if (n <= 1) 1L else n * factorial(n - 1)   // depth n, O(n)

fun fib(n: Int): Long = if (n < 2) n.toLong() else fib(n - 1) + fib(n - 2) // O(φ^n) ≈ O(1.618^n)

java

long factorial(int n) { return n <= 1 ? 1L : n * factorial(n - 1); }      // depth n, O(n)

long fib(int n) { return n < 2 ? n : fib(n - 1) + fib(n - 2); }            // O(φ^n) ≈ O(1.618^n)

fib(5) computes fib(3) twice, fib(2) three times — the tree has O(φ^n) nodes because subproblems overlap. Caching each fib(k) collapses it to O(n). Hold that thought: overlapping subproblems + memoize = DP is the whole bridge in §6.

Reverse in place — recursion as a two-pointer converge (base case: pointers meet):

kotlin

fun reverse(a: CharArray, lo: Int = 0, hi: Int = a.size - 1) {
    if (lo >= hi) return                       // base case
    val t = a[lo]; a[lo] = a[hi]; a[hi] = t     // combine: swap ends
    reverse(a, lo + 1, hi - 1)                  // recurse inward
}

Fast exponentiation — a^n in O(log n) (halve the exponent, square the result). The senior move whenever you see "compute a power": don't loop n times.

kotlin

fun power(base: Long, exp: Int): Long {
    if (exp == 0) return 1L                      // base case
    val half = power(base, exp / 2)              // one call, not two — trust it
    return if (exp % 2 == 0) half * half else half * half * base
}

java

long power(long base, int exp) {
    if (exp == 0) return 1L;                      // base case
    long half = power(base, exp / 2);            // one call, not two — trust it
    return exp % 2 == 0 ? half * half : half * half * base;
}

Computing half once and squaring is what makes it O(log n); power(base, exp/2) * power(base, exp/2) would be O(n) (two recursive calls → the fib trap again).

Towers of Hanoi — the archetypal "solve it by trusting two smaller solves." Move n−1 off, move the big disk, move n−1 back. 2^n − 1 moves, which is provably optimal:

kotlin

fun hanoi(n: Int, from: Char, to: Char, via: Char, moves: MutableList<String>) {
    if (n == 0) return
    hanoi(n - 1, from, via, to, moves)   // shift top n-1 to the spare peg
    moves.add("$from->$to")              // move the largest disk
    hanoi(n - 1, via, to, from, moves)   // shift the n-1 stack onto it
}

java

void hanoi(int n, char from, char to, char via, List<String> moves) {
    if (n == 0) return;
    hanoi(n - 1, from, via, to, moves);  // shift top n-1 to the spare peg
    moves.add(from + "->" + to);         // move the largest disk
    hanoi(n - 1, via, to, from, moves);  // shift the n-1 stack onto it
}

Tail recursion — Kotlin tailrec vs the JVM. A tail-recursive call is the last action in the function. The JVM won't optimize it away; Kotlin will, if you mark it:

kotlin

tailrec fun sumTo(n: Int, acc: Long = 0): Long =    // compiles to a plain loop — no stack growth
    if (n == 0) acc else sumTo(n - 1, acc + n)      // the recursive call is the whole else-branch

Java has no equivalent — a deep tail recursion there overflows, so you rewrite it as a while loop yourself. That is the version-dependent fact to state out loud: "Kotlin tailrec eliminates this; on the JVM in Java I'd make it iterative."

Complexity of the warm-ups. factorial/reverse/power/tailrec-sum: O(depth) time, O(depth) stack (power is O(log n) both). Naive fib: O(φ^n) time. Hanoi: O(2^n) moves (inherent — it's the output size).

Traps. (1) Missing/insufficient base case → infinite recursion → StackOverflowError. (2) Recursing without shrinking toward the base case (same or larger input) → same. (3) Assuming the JVM does TCO — it does not; unbounded depth needs tailrec (Kotlin) or an explicit loop. (4) Naive fib-shaped double recursion over overlapping subproblems is exponential — memoize (guide 05).

2. The backtracking template#

Backtracking is DFS over the partial-solution tree. One skeleton drives every problem in this guide; the only things that change are what a complete solution is, what the choices are at each step, and which choices to prune. Read the seven numbered steps, then see them made concrete and runnable as subsets (records at every node — the cleanest illustration of the shape):

Base case — the partial solution is complete → record it and return.
Record a copy — never the live mutable buffer.
Iterate the choices available at this position (often for i in start until n).
Prune — continue/break on a choice that can’t lead to a valid/optimal solution.
Choose — apply the choice to the partial solution (and any auxiliary state).
Recurse into the smaller subproblem.
Un-choose — undo the choice so the buffer is pristine for the next iteration.

kotlin

fun subsets(nums: IntArray): List<List<Int>> {
    val result = ArrayList<List<Int>>()
    val path = ArrayList<Int>()
    fun backtrack(start: Int) {
        result.add(ArrayList(path))               // 1+2. every node is a valid subset → RECORD A COPY
        for (i in start until nums.size) {         // 3. choices: elements from `start` onward (forward only)
            // 4. (subsets prune nothing; constrained problems `continue`/`break` here)
            path.add(nums[i])                      // 5. CHOOSE nums[i]
            backtrack(i + 1)                       // 6. RECURSE with next start ⇒ no element reused
            path.removeAt(path.size - 1)           // 7. UN-CHOOSE (restore path)
        }
    }
    backtrack(0)
    return result
}

java

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(0, nums, new ArrayList<>(), result);
    return result;
}
private void backtrack(int start, int[] nums, List<Integer> path, List<List<Integer>> result) {
    result.add(new ArrayList<>(path));             // 1+2. RECORD A COPY
    for (int i = start; i < nums.length; i++) {    // 3. choices from `start` onward
        path.add(nums[i]);                         // 5. CHOOSE
        backtrack(i + 1, nums, path, result);      // 6. RECURSE (i+1 ⇒ no reuse)
        path.remove(path.size() - 1);              // 7. UN-CHOOSE
    }
}

Why start and not a fresh 0..n each level? Passing i + 1 (or i) as the next start enforces an ordering on choices, so {1,2} is generated but {2,1} is not. That is exactly what separates combinations/subsets (order-insensitive, use a start index) from permutations (order matters, use every remaining element via used[] or swap). Pick the wrong one and you either miss results or generate duplicates — the first fork in the road for any backtracking problem.

Two dials on the skeleton define the whole taxonomy: (a) start index vs used[] — do choices have an order? — and (b) i vs i + 1 for the next start — may an element be reused? The rest is base case and pruning.

3. Subsets and combinations#

Recognition cue. "Generate/return ALL subsets / combinations / ways to choose"; a target reached by picking a subset of numbers; anything where the order of chosen items does not matter. Solution size is 2^n (subsets) or C(n,k) (fixed size) — exponential, so the constraints will be small (n ≲ 20).

All subsets — two equivalent templates#

Start-index method is the §2 skeleton (records at every node). The other canonical form is the include/exclude binary tree — at each index, branch on "take it or not," record only at the leaf i == n:

kotlin

fun subsetsBinary(nums: IntArray): List<List<Int>> {
    val result = ArrayList<List<Int>>()
    val path = ArrayList<Int>()
    fun dfs(i: Int) {
        if (i == nums.size) { result.add(ArrayList(path)); return }  // leaf = one full decision
        dfs(i + 1)                              // branch A: EXCLUDE nums[i]
        path.add(nums[i])                       // branch B: INCLUDE nums[i]
        dfs(i + 1)
        path.removeAt(path.size - 1)            // un-choose
    }
    dfs(0)
    return result
}

java

private void dfs(int i, int[] nums, List<Integer> path, List<List<Integer>> result) {
    if (i == nums.length) { result.add(new ArrayList<>(path)); return; } // leaf = one full decision
    dfs(i + 1, nums, path, result);             // branch A: EXCLUDE nums[i]
    path.add(nums[i]);                          // branch B: INCLUDE nums[i]
    dfs(i + 1, nums, path, result);
    path.remove(path.size() - 1);              // un-choose
}

Both emit the same 2^n subsets. The start-index form generalizes directly to combinations and combination-sum; the include/exclude form is the mental bridge to knapsack DP (guide 05). Know both; lead with start-index.

Subsets II — duplicates via sort + skip-at-same-level#

With duplicate values, the fix is universal: sort, then within one for loop skip a value equal to its predecessor (i > start). That kills sibling branches that would regenerate an identical subset, while still allowing a duplicate deeper in the tree.

kotlin

fun subsetsWithDup(nums: IntArray): List<List<Int>> {
    nums.sort()
    val result = ArrayList<List<Int>>()
    val path = ArrayList<Int>()
    fun backtrack(start: Int) {
        result.add(ArrayList(path))
        for (i in start until nums.size) {
            if (i > start && nums[i] == nums[i - 1]) continue   // skip dup at THIS tree level
            path.add(nums[i]); backtrack(i + 1); path.removeAt(path.size - 1)
        }
    }
    backtrack(0)
    return result
}

java

public List<List<Integer>> subsetsWithDup(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> result = new ArrayList<>();
    backtrack(0, nums, new ArrayList<>(), result);
    return result;
}
private void backtrack(int start, int[] nums, List<Integer> path, List<List<Integer>> result) {
    result.add(new ArrayList<>(path));
    for (int i = start; i < nums.length; i++) {
        if (i > start && nums[i] == nums[i - 1]) continue;      // skip dup at THIS tree level
        path.add(nums[i]); backtrack(i + 1, nums, path, result); path.remove(path.size() - 1);
    }
}

The i > start is load-bearing: it skips a duplicate only when it is a sibling of an already-tried value (same parent), not when it legitimately extends the path.

Combinations — n choose k (fixed depth + count pruning)#

Recognition cue. "All combinations of size k." Base case is path.size == k. Add a feasibility prune: if the elements remaining can't fill the remaining slots, break.

kotlin

fun combine(n: Int, k: Int): List<List<Int>> {
    val result = ArrayList<List<Int>>()
    val path = ArrayList<Int>()
    fun backtrack(start: Int) {
        if (path.size == k) { result.add(ArrayList(path)); return }
        for (i in start..n) {
            if (n - i + 1 < k - path.size) break     // not enough numbers left to reach size k → prune
            path.add(i); backtrack(i + 1); path.removeAt(path.size - 1)
        }
    }
    backtrack(1)
    return result
}

java

public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(1, n, k, new ArrayList<>(), result);
    return result;
}
private void backtrack(int start, int n, int k, List<Integer> path, List<List<Integer>> result) {
    if (path.size() == k) { result.add(new ArrayList<>(path)); return; }
    for (int i = start; i <= n; i++) {
        if (n - i + 1 < k - path.size()) break;      // not enough numbers left → prune
        path.add(i); backtrack(i + 1, n, k, path, result); path.remove(path.size() - 1);
    }
}

That one break turns a lot of dead subtrees into nothing; without it you still recurse into branches that can never reach size k.

Combination Sum — reuse vs no-reuse is one character#

Combination Sum (LC 39) allows reusing an element unlimited times → recurse with i, not i + 1. Sort so candidates[i] > remain can break:

kotlin

fun combinationSum(candidates: IntArray, target: Int): List<List<Int>> {
    candidates.sort()
    val result = ArrayList<List<Int>>()
    val path = ArrayList<Int>()
    fun backtrack(start: Int, remain: Int) {
        if (remain == 0) { result.add(ArrayList(path)); return }
        for (i in start until candidates.size) {
            if (candidates[i] > remain) break            // sorted ⇒ all later are too big, prune
            path.add(candidates[i])
            backtrack(i, remain - candidates[i])         // i (NOT i+1) ⇒ reuse allowed
            path.removeAt(path.size - 1)
        }
    }
    backtrack(0, target)
    return result
}

java

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    Arrays.sort(candidates);
    List<List<Integer>> result = new ArrayList<>();
    backtrack(0, target, candidates, new ArrayList<>(), result);
    return result;
}
private void backtrack(int start, int remain, int[] candidates,
                       List<Integer> path, List<List<Integer>> result) {
    if (remain == 0) { result.add(new ArrayList<>(path)); return; }
    for (int i = start; i < candidates.length; i++) {
        if (candidates[i] > remain) break;               // sorted ⇒ later too big, prune
        path.add(candidates[i]);
        backtrack(i, remain - candidates[i], candidates, path, result);  // i ⇒ reuse
        path.remove(path.size() - 1);
    }
}

Combination Sum II (LC 40) — each element used once and the input has duplicates. Two edits to the above: recurse with i + 1 (no reuse) and add the sort + skip-at-level dedup line:

kotlin

fun combinationSum2(candidates: IntArray, target: Int): List<List<Int>> {
    candidates.sort()
    val result = ArrayList<List<Int>>()
    val path = ArrayList<Int>()
    fun backtrack(start: Int, remain: Int) {
        if (remain == 0) { result.add(ArrayList(path)); return }
        for (i in start until candidates.size) {
            if (candidates[i] > remain) break
            if (i > start && candidates[i] == candidates[i - 1]) continue   // dedup at level
            path.add(candidates[i])
            backtrack(i + 1, remain - candidates[i])                        // i+1 ⇒ used once
            path.removeAt(path.size - 1)
        }
    }
    backtrack(0, target)
    return result
}

(The Java is combinationSum with those same two edits — i + 1 in the recurse and the i > start && ==prev skip.) These two problems next to each other are the "start index" lesson: i reuses, i+1 does not; sort+skip dedups duplicate inputs.

Letter combinations of a phone number (LC 17)#

Recognition cue. Cartesian product across positions — each digit contributes one letter from a fixed set. Depth = number of digits, branching = letters per digit:

kotlin

fun letterCombinations(digits: String): List<String> {
    if (digits.isEmpty()) return emptyList()
    val map = arrayOf("", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz")
    val result = ArrayList<String>()
    val sb = StringBuilder()                          // the path, as a char buffer
    fun backtrack(idx: Int) {
        if (idx == digits.length) { result.add(sb.toString()); return }
        for (ch in map[digits[idx] - '0']) {
            sb.append(ch); backtrack(idx + 1); sb.deleteCharAt(sb.length - 1)  // choose / recurse / un-choose
        }
    }
    backtrack(0)
    return result
}

java

public List<String> letterCombinations(String digits) {
    if (digits.isEmpty()) return new ArrayList<>();
    String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    List<String> result = new ArrayList<>();
    backtrack(0, digits, map, new StringBuilder(), result);
    return result;
}
private void backtrack(int idx, String digits, String[] map, StringBuilder sb, List<String> result) {
    if (idx == digits.length()) { result.add(sb.toString()); return; }
    String letters = map[digits.charAt(idx) - '0'];
    for (int j = 0; j < letters.length(); j++) {
        sb.append(letters.charAt(j)); backtrack(idx + 1, digits, map, sb, result); sb.deleteCharAt(sb.length() - 1);
    }
}

Using a single StringBuilder as the mutable path (append = choose, deleteCharAt = un-choose) avoids allocating a string per node — only the leaf sb.toString() copies.

Complexity. Subsets: O(2^n · n) time (2^n subsets, O(n) to copy each), O(n) stack. Combinations: O(k · C(n,k)). Combination Sum: exponential in target/min(candidate) depth. Letter combos: O(4^n · n) (≤4 letters per digit).

Traps. (1) Recording the reference result.add(path) instead of a copy → all results alias the same list. (2) Duplicates: forgetting to sort, or writing the skip as i > 0 instead of i > start (that wrongly kills valid deep duplicates). (3) Reuse bug: i vs i + 1 — passing the wrong one silently allows/forbids reuse. (4) Combination-sum without the sorted break → TLE on adversarial targets.

4. Permutations#

Recognition cue. "All permutations / orderings / arrangements." Now order matters, so you can't use a forward-only start index — every unused element is a candidate at every position. Two encodings: a used[] boolean array, or in-place swapping.

All permutations — `used[]` (LC 46)#

kotlin

fun permute(nums: IntArray): List<List<Int>> {
    val result = ArrayList<List<Int>>()
    val path = ArrayList<Int>()
    val used = BooleanArray(nums.size)
    fun backtrack() {
        if (path.size == nums.size) { result.add(ArrayList(path)); return }
        for (i in nums.indices) {
            if (used[i]) continue                        // skip already-placed elements
            used[i] = true; path.add(nums[i])            // choose
            backtrack()                                  // recurse
            path.removeAt(path.size - 1); used[i] = false // un-choose (BOTH parts)
        }
    }
    backtrack()
    return result
}

java

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    boolean[] used = new boolean[nums.length];
    backtrack(nums, used, new ArrayList<>(), result);
    return result;
}
private void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> result) {
    if (path.size() == nums.length) { result.add(new ArrayList<>(path)); return; }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;                           // skip already-placed
        used[i] = true; path.add(nums[i]);               // choose
        backtrack(nums, used, path, result);             // recurse
        path.remove(path.size() - 1); used[i] = false;   // un-choose (BOTH parts)
    }
}

The un-choose has two halves here — pop the path and clear used[i]. Forgetting the second is the classic "shared visited not reset" bug: the array stays dirty and later branches see phantom used slots.

Permutations by in-place swap — O(1) extra state#

Swap element start with each i ≥ start, recurse on start + 1, swap back. No used[], no path buffer — the array itself is the partial solution (Kotlin shown; the Java is the same three swaps):

kotlin

fun permuteSwap(nums: IntArray): List<List<Int>> {
    val result = ArrayList<List<Int>>()
    fun swap(a: Int, b: Int) { val t = nums[a]; nums[a] = nums[b]; nums[b] = t }
    fun backtrack(start: Int) {
        if (start == nums.size) { result.add(nums.toList()); return }
        for (i in start until nums.size) {
            swap(start, i)              // choose: put nums[i] at position `start`
            backtrack(start + 1)
            swap(start, i)              // un-choose: put it back
        }
    }
    backtrack(0)
    return result
}

Swap-based permutation is O(1) auxiliary space but does not emit lexicographic order and does not naturally dedup — prefer used[] when you need either.

Permutations II — duplicates (LC 47)#

Sort, then the dedup rule for permutations differs from subsets: skip nums[i] if it equals nums[i-1] and the predecessor is not currently used (!used[i-1]). That forces equal elements to be placed in left-to-right order, so each distinct multiset order is generated once:

kotlin

fun permuteUnique(nums: IntArray): List<List<Int>> {
    nums.sort()
    val result = ArrayList<List<Int>>()
    val path = ArrayList<Int>()
    val used = BooleanArray(nums.size)
    fun backtrack() {
        if (path.size == nums.size) { result.add(ArrayList(path)); return }
        for (i in nums.indices) {
            if (used[i]) continue
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue  // fix order among equals
            used[i] = true; path.add(nums[i]); backtrack()
            path.removeAt(path.size - 1); used[i] = false
        }
    }
    backtrack()
    return result
}

java

public List<List<Integer>> permuteUnique(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> result = new ArrayList<>();
    boolean[] used = new boolean[nums.length];
    backtrack(nums, used, new ArrayList<>(), result);
    return result;
}
private void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> result) {
    if (path.size() == nums.length) { result.add(new ArrayList<>(path)); return; }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;   // fix order among equals
        used[i] = true; path.add(nums[i]); backtrack(nums, used, path, result);
        path.remove(path.size() - 1); used[i] = false;
    }
}

Note the asymmetry worth saying aloud: subsets dedup with i > start, permutations dedup with !used[i-1] — same idea (don't start two sibling branches with the same value) but a different test because permutations revisit all indices while subsets march forward.

String permutations are permuteUnique on a sorted CharArray with a StringBuilder buffer — identical skeleton:

kotlin

fun stringPermutations(s: String): List<String> {
    val ch = s.toCharArray().also { it.sort() }
    val result = ArrayList<String>(); val sb = StringBuilder(); val used = BooleanArray(ch.size)
    fun backtrack() {
        if (sb.length == ch.size) { result.add(sb.toString()); return }
        for (i in ch.indices) {
            if (used[i] || (i > 0 && ch[i] == ch[i - 1] && !used[i - 1])) continue
            used[i] = true; sb.append(ch[i]); backtrack()
            sb.deleteCharAt(sb.length - 1); used[i] = false
        }
    }
    backtrack()
    return result
}

Next permutation — the iterative in-place algorithm (LC 31)#

Recognition cue. "Next lexicographic arrangement," or an interviewer explicitly rules out generating all n!. This is not backtracking — it’s a four-step O(n) rewrite you should memorize:

Scan from the right for the first i with nums[i] < nums[i+1] (the pivot — the rightmost element that can be increased).
If none exists, the array is the last permutation → reverse the whole thing (wrap to first).
Else scan from the right for the first j with nums[j] > nums[i]; swap i and j.
Reverse the suffix after i (it was descending; reversing makes it the smallest tail).

kotlin

fun nextPermutation(nums: IntArray) {
    var i = nums.size - 2
    while (i >= 0 && nums[i] >= nums[i + 1]) i--          // 1. find the pivot
    if (i >= 0) {                                          // 2. (i < 0 ⇒ last perm, just reverse all)
        var j = nums.size - 1
        while (nums[j] <= nums[i]) j--                     // 3. rightmost value greater than pivot
        val t = nums[i]; nums[i] = nums[j]; nums[j] = t    //    swap
    }
    var lo = i + 1; var hi = nums.size - 1                 // 4. reverse the suffix
    while (lo < hi) { val t = nums[lo]; nums[lo] = nums[hi]; nums[hi] = t; lo++; hi-- }
}

java

public void nextPermutation(int[] nums) {
    int i = nums.length - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) i--;          // 1. pivot
    if (i >= 0) {                                          // 2.
        int j = nums.length - 1;
        while (nums[j] <= nums[i]) j--;                    // 3. rightmost value > pivot
        int t = nums[i]; nums[i] = nums[j]; nums[j] = t;   //    swap
    }
    int lo = i + 1, hi = nums.length - 1;                  // 4. reverse suffix
    while (lo < hi) { int t = nums[lo]; nums[lo] = nums[hi]; nums[hi] = t; lo++; hi--; }
}

Complexity. Permutations: O(n! · n) time, O(n) stack + O(n) used. Next permutation: O(n) time, O(1) space.

Traps. (1) used not reset on un-choose → later branches lose elements. (2) Permutations dedup written as i > start (subsets rule) — wrong; use !used[i-1]. (3) Next-permutation: forgetting to reverse the suffix, or using >=/<= inconsistently (equal elements must not count as an ascent, or duplicates break lexicographic order).

5. Grid and constraint backtracking#

Same skeleton, richer state: a board, a set of occupied columns, a running counter. The theme is prune with the constraint itself — never build an invalid partial candidate.

Generate parentheses (LC 22) — counters are the pruning#

Recognition cue. Build all valid strings under a balance constraint. Track open/close counts; you may open while open < n, and close only while close < open. Those two guards mean every string you ever build is valid — no post-hoc filtering:

kotlin

fun generateParenthesis(n: Int): List<String> {
    val result = ArrayList<String>(); val sb = StringBuilder()
    fun backtrack(open: Int, close: Int) {
        if (sb.length == 2 * n) { result.add(sb.toString()); return }
        if (open < n) {                                   // can still place '('
            sb.append('('); backtrack(open + 1, close); sb.deleteCharAt(sb.length - 1)
        }
        if (close < open) {                               // can close only an unmatched '('
            sb.append(')'); backtrack(open, close + 1); sb.deleteCharAt(sb.length - 1)
        }
    }
    backtrack(0, 0)
    return result
}

java

public List<String> generateParenthesis(int n) {
    List<String> result = new ArrayList<>();
    backtrack(0, 0, n, new StringBuilder(), result);
    return result;
}
private void backtrack(int open, int close, int n, StringBuilder sb, List<String> result) {
    if (sb.length() == 2 * n) { result.add(sb.toString()); return; }
    if (open < n)     { sb.append('('); backtrack(open + 1, close, n, sb, result); sb.deleteCharAt(sb.length() - 1); }
    if (close < open) { sb.append(')'); backtrack(open, close + 1, n, sb, result); sb.deleteCharAt(sb.length() - 1); }
}

Word search (LC 79) — DFS on a grid with mark / un-mark#

Recognition cue. Spell a word along 4-adjacent cells, each cell used once per path. Mark the current cell (overwrite or a visited[][]), recurse the four directions, then un-mark so other paths may reuse it:

kotlin

fun exist(board: Array<CharArray>, word: String): Boolean {
    val rows = board.size; val cols = board[0].size
    fun dfs(r: Int, c: Int, k: Int): Boolean {
        if (k == word.length) return true                                   // matched all chars
        if (r !in 0 until rows || c !in 0 until cols || board[r][c] != word[k]) return false
        val saved = board[r][c]; board[r][c] = '#'                          // mark visited
        val found = dfs(r + 1, c, k + 1) || dfs(r - 1, c, k + 1) ||
                    dfs(r, c + 1, k + 1) || dfs(r, c - 1, k + 1)
        board[r][c] = saved                                                 // UN-mark (backtrack)
        return found
    }
    for (r in 0 until rows) for (c in 0 until cols) if (dfs(r, c, 0)) return true
    return false
}

java

public boolean exist(char[][] board, String word) {
    for (int r = 0; r < board.length; r++)
        for (int c = 0; c < board[0].length; c++)
            if (dfs(board, r, c, word, 0)) return true;
    return false;
}
private boolean dfs(char[][] board, int r, int c, String word, int k) {
    if (k == word.length()) return true;                                    // matched all chars
    if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] != word.charAt(k))
        return false;
    char saved = board[r][c]; board[r][c] = '#';                            // mark visited
    boolean found = dfs(board, r + 1, c, word, k + 1) || dfs(board, r - 1, c, word, k + 1)
                 || dfs(board, r, c + 1, word, k + 1) || dfs(board, r, c - 1, word, k + 1);
    board[r][c] = saved;                                                    // UN-mark (backtrack)
    return found;
}

The board[r][c] = saved restore is what makes this backtracking rather than a plain flood fill. Omit it and a cell consumed on one dead path is unavailable to a valid path — you get false negatives. (Grid DFS mechanics — the direction idiom, in-place marking — are covered as traversal in guide 03; here the point is the un-mark step.)

N-Queens (LC 51) — one queen per row, O(1) conflict sets#

Recognition cue. Place items so none attack each other. Place one queen per row; a column c at row r is safe iff c, the diagonal r − c, and the anti-diagonal r + c are all free. Three HashSets give O(1) checks and O(1) choose/un-choose:

kotlin

fun solveNQueens(n: Int): List<List<String>> {
    val result = ArrayList<List<String>>()
    val cols = HashSet<Int>(); val diag = HashSet<Int>(); val anti = HashSet<Int>()  // r-c and r+c
    val board = Array(n) { CharArray(n) { '.' } }
    fun backtrack(r: Int) {
        if (r == n) { result.add(board.map { String(it) }); return }
        for (c in 0 until n) {
            if (c in cols || (r - c) in diag || (r + c) in anti) continue   // pruned: under attack
            cols.add(c); diag.add(r - c); anti.add(r + c); board[r][c] = 'Q' // choose
            backtrack(r + 1)                                                 // recurse to next row
            cols.remove(c); diag.remove(r - c); anti.remove(r + c); board[r][c] = '.' // un-choose
        }
    }
    backtrack(0)
    return result
}

java

public List<List<String>> solveNQueens(int n) {
    List<List<String>> result = new ArrayList<>();
    Set<Integer> cols = new HashSet<>(), diag = new HashSet<>(), anti = new HashSet<>();
    char[][] board = new char[n][n];
    for (char[] row : board) Arrays.fill(row, '.');
    backtrack(0, n, cols, diag, anti, board, result);
    return result;
}
private void backtrack(int r, int n, Set<Integer> cols, Set<Integer> diag, Set<Integer> anti,
                       char[][] board, List<List<String>> result) {
    if (r == n) {
        List<String> sol = new ArrayList<>();
        for (char[] row : board) sol.add(new String(row));
        result.add(sol); return;
    }
    for (int c = 0; c < n; c++) {
        if (cols.contains(c) || diag.contains(r - c) || anti.contains(r + c)) continue; // under attack
        cols.add(c); diag.add(r - c); anti.add(r + c); board[r][c] = 'Q';   // choose
        backtrack(r + 1, n, cols, diag, anti, board, result);               // recurse
        cols.remove(c); diag.remove(r - c); anti.remove(r + c); board[r][c] = '.'; // un-choose
    }
}

The r − c / r + c trick is the interview flex: cells on one ↘ diagonal share r − c; cells on one ↙ anti-diagonal share r + c. For the count variant (LC 52, N-Queens II) drop the board and just increment a counter at r == n.

Sudoku solver (LC 37) — try, recurse, undo on the first empty cell#

Recognition cue. Fill a constrained grid completely. Find the first empty cell, try each legal digit, recurse; if the recursion fails, undo and try the next digit. Returning true up the stack the moment a full board is found stops the search:

kotlin

fun solveSudoku(board: Array<CharArray>) {
    fun isValid(r: Int, c: Int, ch: Char): Boolean {
        for (i in 0 until 9) {
            if (board[r][i] == ch) return false                        // row
            if (board[i][c] == ch) return false                        // column
            if (board[3 * (r / 3) + i / 3][3 * (c / 3) + i % 3] == ch) return false  // 3x3 box
        }
        return true
    }
    fun solve(): Boolean {
        for (r in 0 until 9) for (c in 0 until 9) if (board[r][c] == '.') {
            for (ch in '1'..'9') if (isValid(r, c, ch)) {
                board[r][c] = ch                                       // choose
                if (solve()) return true                               // recurse; propagate success
                board[r][c] = '.'                                      // un-choose
            }
            return false                                               // no digit fits ⇒ dead end
        }
        return true                                                    // no empty cell ⇒ solved
    }
    solve()
}

java

public void solveSudoku(char[][] board) { solve(board); }
private boolean solve(char[][] board) {
    for (int r = 0; r < 9; r++) for (int c = 0; c < 9; c++) if (board[r][c] == '.') {
        for (char ch = '1'; ch <= '9'; ch++) if (isValid(board, r, c, ch)) {
            board[r][c] = ch;                                          // choose
            if (solve(board)) return true;                            // recurse; propagate success
            board[r][c] = '.';                                        // un-choose
        }
        return false;                                                 // no digit fits ⇒ dead end
    }
    return true;                                                      // solved
}
private boolean isValid(char[][] board, int r, int c, char ch) {
    for (int i = 0; i < 9; i++) {
        if (board[r][i] == ch) return false;
        if (board[i][c] == ch) return false;
        if (board[3 * (r / 3) + i / 3][3 * (c / 3) + i % 3] == ch) return false;
    }
    return true;
}

The box index 3*(r/3)+i/3, 3*(c/3)+i%3 walks the nine cells of the block containing (r,c). This is a decision problem (find one solution), so it returns boolean and short-circuits — unlike the enumeration problems above that collect into a list.

Splitting a string — palindrome partitioning (LC 131), restore IP (LC 93)#

Recognition cue. Cut a string into pieces each satisfying a predicate. The choice at each step is where to cut next; recurse on the remainder; only descend when the prefix is valid (feasibility pruning).

kotlin

fun partition(s: String): List<List<String>> {
    val result = ArrayList<List<String>>(); val path = ArrayList<String>()
    fun isPalindrome(lo: Int, hi: Int): Boolean {
        var l = lo; var h = hi
        while (l < h) { if (s[l] != s[h]) return false; l++; h-- }
        return true
    }
    fun backtrack(start: Int) {
        if (start == s.length) { result.add(ArrayList(path)); return }
        for (end in start until s.length) if (isPalindrome(start, end)) {   // prune: only palindromic prefixes
            path.add(s.substring(start, end + 1)); backtrack(end + 1); path.removeAt(path.size - 1)
        }
    }
    backtrack(0)
    return result
}

java

public List<List<String>> partition(String s) {
    List<List<String>> result = new ArrayList<>();
    backtrack(0, s, new ArrayList<>(), result);
    return result;
}
private void backtrack(int start, String s, List<String> path, List<List<String>> result) {
    if (start == s.length()) { result.add(new ArrayList<>(path)); return; }
    for (int end = start; end < s.length(); end++) if (isPalindrome(s, start, end)) {  // prune
        path.add(s.substring(start, end + 1)); backtrack(end + 1, s, path, result); path.remove(path.size() - 1);
    }
}
private boolean isPalindrome(String s, int lo, int hi) {
    while (lo < hi) if (s.charAt(lo++) != s.charAt(hi--)) return false;
    return true;
}

Restore IP addresses is the same shape with a fixed part count (4) and richer per-segment validity — length 1–3, no leading zero, value ≤ 255. The breaks prune whole subtrees:

kotlin

fun restoreIpAddresses(s: String): List<String> {
    val result = ArrayList<String>(); val parts = ArrayList<String>()
    fun backtrack(start: Int) {
        if (parts.size == 4) { if (start == s.length) result.add(parts.joinToString(".")); return }
        for (len in 1..3) {
            if (start + len > s.length) break
            val seg = s.substring(start, start + len)
            if (len > 1 && seg[0] == '0') break        // no leading zero (longer also invalid)
            if (seg.toInt() > 255) break               // out of range (longer also larger)
            parts.add(seg); backtrack(start + len); parts.removeAt(parts.size - 1)
        }
    }
    backtrack(0)
    return result
}

java

public List<String> restoreIpAddresses(String s) {
    List<String> result = new ArrayList<>();
    backtrack(0, s, new ArrayList<>(), result);
    return result;
}
private void backtrack(int start, String s, List<String> parts, List<String> result) {
    if (parts.size() == 4) { if (start == s.length()) result.add(String.join(".", parts)); return; }
    for (int len = 1; len <= 3; len++) {
        if (start + len > s.length()) break;
        String seg = s.substring(start, start + len);
        if (len > 1 && seg.charAt(0) == '0') break;    // no leading zero
        if (Integer.parseInt(seg) > 255) break;        // out of range
        parts.add(seg); backtrack(start + len, s, parts, result); parts.remove(parts.size() - 1);
    }
}

Complexity. Generate parens: O(4^n / √n) (the Catalan number of valid strings) × O(n) copy. Word search: O(R·C · 3^L) — from any start, ≤3 onward directions for L steps. N-Queens: bounded by O(n!), far less with the three-set pruning. Sudoku: O(9^E) worst case (E = empty cells), tiny in practice. Palindrome partition: O(2^n · n) (a cut or not between each pair). Restore IP: O(1) — at most 3^4 segmentations.

Traps. (1) Word search without un-mark → false negatives (cell stuck as visited). (2) N-Queens using a boolean[n][n] and scanning for attacks each placement → O(n) per check and easy off-by-one; the three sets are cleaner and O(1). (3) Sudoku forgetting to reset the cell on failure, or not propagating the true return (searching on after a solution). (4) Restore-IP treating "0" as invalid (it's valid; only multi-digit leading-zero segments are illegal).

6. Pruning, and the bridge to DP#

Pruning is the whole performance story#

Backtracking’s node count is branching^depth; pruning cuts subtrees so the effective count is far smaller. Three levers, in order of impact:

Feasibility / bound pruning. Stop the moment the partial candidate can't be completed: combination-sum’s sorted break on candidates[i] > remain; combinations’ "not enough numbers left"; restore-IP’s range/length break. On an optimization problem, also prune when the best still achievable can’t beat the incumbent (branch-and-bound).
Order choices to prune early. Sorting so the failing break fires sooner, or trying the most-constrained position first (Sudoku: pick the empty cell with the fewest legal digits — the "minimum remaining values" heuristic — to fail fast and shrink branching).
Symmetry breaking. Don’t explore mirror-image branches. N-Queens can fix the first queen to the left half of row 0 and reflect. The sort+skip dedup lines in §3–§4 are symmetry breaking: they forbid re-generating an equivalent arrangement.

When is backtracking the intended solution? Read the constraints (guide 00’s constraint table). Exponential enumeration is only viable when n is small — roughly n ≲ 20 for 2^n, n ≲ 10–11 for n!. If you see n ≤ 15 and "return all …" or "place under constraints," the interviewer is asking for backtracking; a polynomial DP either doesn’t exist or isn’t what’s wanted. Conversely n = 10^5 rules backtracking out — that’s a greedy/DP/graph tell.

How this maps to your world (optional): exhaustive constraint search shows up wherever a small config space must satisfy hard rules — e.g. "which subset of OCPI version read-models / connector-tariff combinations satisfies every party constraint" is a backtracking/constraint-satisfaction search when the option set is tiny. The instant those sub-decisions start overlapping (the same partial config reached many ways), you stop enumerating and memoize — which is the next paragraph.

The bridge to DP: memoize a backtracking recursion#

This is the single most important connection to guide 05. A backtracking search that returns a value (a boolean "can we?", a count "how many ways?", an optimum) and whose recursion reaches the same state via many different paths has overlapping subproblems — exactly fib’s pathology at scale. Cache the return value keyed by the state and the exponential search collapses to polynomial. That cache is top-down DP.

Word Break (LC 139) is the cleanest demonstration. Pure backtracking — try every prefix in the dictionary, recurse on the rest:

kotlin

fun wordBreakBrute(s: String, wordDict: List<String>): Boolean {
    val dict = wordDict.toHashSet()
    fun canBreak(start: Int): Boolean {
        if (start == s.length) return true
        for (end in start + 1..s.length)
            if (s.substring(start, end) in dict && canBreak(end)) return true
        return false
    }
    return canBreak(0)                     // EXPONENTIAL: canBreak(end) recomputed for every path to `end`
}

On input like "aaaa…a" + "b" this is O(2^n) — canBreak(end) is recomputed once per distinct path that reaches index end, and there are exponentially many. But the answer for a given start never changes. Cache it — one line — and it’s O(n²·L):

kotlin

fun wordBreak(s: String, wordDict: List<String>): Boolean {
    val dict = wordDict.toHashSet()
    val memo = HashMap<Int, Boolean>()      // STATE = start index → answer (this map is the DP table)
    fun canBreak(start: Int): Boolean {
        if (start == s.length) return true
        memo[start]?.let { return it }      // reuse the overlapping subresult
        for (end in start + 1..s.length)
            if (s.substring(start, end) in dict && canBreak(end)) { memo[start] = true; return true }
        memo[start] = false
        return false
    }
    return canBreak(0)
}

java

public boolean wordBreak(String s, List<String> wordDict) {
    Set<String> dict = new HashSet<>(wordDict);
    Boolean[] memo = new Boolean[s.length() + 1];   // STATE = start index → answer
    return canBreak(0, s, dict, memo);
}
private boolean canBreak(int start, String s, Set<String> dict, Boolean[] memo) {
    if (start == s.length()) return true;
    if (memo[start] != null) return memo[start];    // reuse the overlapping subresult
    for (int end = start + 1; end <= s.length(); end++)
        if (dict.contains(s.substring(start, end)) && canBreak(end, s, dict, memo))
            return memo[start] = true;
    return memo[start] = false;
}

The contrast, stated precisely — this is what to say in an interview:

	Backtracking (enumerate)	Top-down DP (memoized recursion)
Goal	list/produce all candidates	compute one value (count / feasibility / optimum)
Subproblem reuse	none — every path is distinct	yes — same state reached many ways
Does memoization help?	No (all `2^n`/`n!` outputs are needed)	Yes — collapses exponential to polynomial
Un-choose needed?	Yes (shared mutable path)	Often not (you return values, don’t mutate a shared buffer)
Examples	subsets, permutations, N-Queens, generate-parens	word break, coin change, edit distance, LIS

So the decision procedure: write the recursion first. If it must emit every combination, it’s backtracking and you’re done. If it returns a value and you can see the same arguments recurring, add a memo keyed by the state — you’ve derived top-down DP, and guide 05 turns that into a bottom-up table.

7. Stating backtracking complexity cleanly#

Always express it as (size of the decision tree) × (work per leaf), and derive the tree size as branching^depth. Saying this out loud is the senior signal — it shows you can bound a search before running it.

Problem	Tree size (leaves/nodes)	× per-node work	Total time	Aux space
Subsets	`2^n` subsets	`O(n)` to copy	`O(2^n · n)`	`O(n)` stack
Permutations	`n!` orderings	`O(n)` to copy	`O(n! · n)`	`O(n)`
Combinations `nCk`	`C(n,k)`	`O(k)` to copy	`O(C(n,k) · k)`	`O(k)`
Combination Sum	≤ `O(n^{target/min})`	`O(target/min)`	exponential	`O(target/min)`
Generate parens	`C_n ≈ 4^n/n^{1.5}` valid	`O(n)`	`O(4^n/√n)`	`O(n)`
Word Search	`R·C` starts × `3^L`	`O(1)`	`O(R·C·3^L)`	`O(L)`
N-Queens	≤ `n!` (pruned to far less)	`O(n)` per solution	`≤ O(n!)`	`O(n)`
Sudoku	≤ `9^E` (`E` empties)	`O(1)` legality	`≤ O(9^E)`	`O(1)`

Two derivations to be able to reproduce on a whiteboard: subsets — each element is independently in or out → 2 · 2 · … · 2 = 2^n leaves, each an O(n) copy. Permutations — n choices for the first slot, n−1 for the next, … → n! leaves, each an O(n) copy. The × n (or × k) factor is the copy into the result and is easy to forget; include it — a sharp interviewer will ask "and the cost to record each?".

Problems & how to solve them#

Problem: every result in the output list is identical (often all empty). Root cause: recording the reference to the mutable path — result.add(path) — instead of a snapshot. All entries point at the one buffer, which the un-choose steps eventually empty. Fix: copy on record — result.add(new ArrayList<>(path)) / result.add(ArrayList(path)), or sb.toString() for a StringBuilder. The copy is the only allocation that must happen at a leaf.

Problem: state leaks between sibling branches; results are polluted / non-deterministic. Root cause: forgetting to un-choose — the path (or used[], or a set, or a marked grid cell) still holds a choice from a subtree you already returned from. Fix: make choose/un-choose symmetric — every mutation before recurse has a matching inverse after it. If you set used[i]=true and path.add, you must clear both. Say the invariant aloud: "after recurse returns, state equals what it was before choose."

Problem: duplicate results ([1,2] and [2,1], or the same subset twice). Root cause: either using a permutation encoding for a combination problem (no start index), or duplicate values in the input with no dedup. Fix: order-insensitive → start index (i+1) so choices only go forward. Duplicate inputs → sort, then skip the appropriate way: i > start && a[i]==a[i-1] for subsets/combinations; i>0 && a[i]==a[i-1] && !used[i-1] for permutations.

Problem: an element is reused when it shouldn’t be (or can’t be reused when it should). Root cause: passing the wrong start index to the recursive call — i (reuse allowed) vs i + 1 (each used once). Fix: pick deliberately. Combination Sum (unlimited reuse) → recurse i. Combination Sum II / combinations / subsets (each once) → recurse i + 1. This one character is the entire difference between LC 39 and LC 40.

Problem: correct but TLE / times out. Root cause: missing feasibility pruning — you descend into subtrees that provably can’t reach a solution (sum already over target, not enough elements left, an out-of-range IP segment). Fix: sort so a break can cut the tail (candidate > remain), add bound checks at the top of the loop, and try the most-constrained choice first. Pruning changes the effective tree size by orders of magnitude without changing correctness.

Problem: a shared visited / marked grid gives wrong answers across starts. Root cause: the shared marker (a boolean[][], or an overwritten grid cell) is not reset after the DFS from one start fails, so the next start sees phantom-visited cells. Fix: restore the marker on the way out (board[r][c] = saved), i.e. treat "visited" as a choice subject to the same un-choose discipline. In word search this restore is the difference between correct and silently wrong.

Problem: StackOverflowError on deep recursion. Root cause: recursion depth exceeds the JVM stack (~a few thousand to tens of thousands of frames); backtracking depth is bounded by n, so this bites only when n is large and branching is 1 (degenerate), or on a pathological grid snake. Fix: for backtracking proper, n is small by construction, so this is rare — but know the escape hatches: convert to an explicit stack, or (Kotlin) tailrec for genuinely tail-recursive helpers, or run on a Thread with a larger stack size. State the depth bound out loud.

Interview framing / how to sound senior#

Draw the decision tree before you code. Say: "Root is the empty candidate; at each node I choose the next element; leaves are complete solutions. Branching is k, depth is n, so O(k^n) nodes — small because n ≤ 15." Naming the tree and its size first is the judgment signal the rubric rewards (guide 00); weak candidates start mutating a list before they can state what a node represents.
State the choose/un-choose invariant explicitly. "I mutate the path to choose, recurse, then undo so the buffer is pristine for the sibling." That one sentence pre-empts the two bugs (leaked state, aliased result) an interviewer is watching for.
Announce the two dials. "Order doesn’t matter, so start index; each element once, so i+1; duplicates in input, so sort + skip." Deriving the template from the problem’s properties — rather than reciting a memorized snippet — is exactly the senior/staff differentiator.
Lead with the constraint-size read. "n ≤ 20 and ‘generate all’ → this is backtracking, not DP." Then, if asked to optimize a counting/feasibility variant: "the recursion has overlapping states, so I’d memoize on (index, …) — that turns it into top-down DP." Volunteering the DP bridge unprompted reads as range.
Quote complexity as tree × work. "2^n subsets times O(n) to copy each = O(2^n · n)" — and don’t drop the copy factor. Then mention the prune: "sorting lets me break early, so the effective tree is much smaller than the bound."
Flag the JVM/version facts. "The JVM doesn’t eliminate tail calls; Kotlin’s tailrec does. Recursion depth here is O(n) and n is tiny, so the stack is fine — otherwise I’d go iterative." Production-readiness thinking is explicitly rewarded on 2026 infra rubrics.
Snowflake-flavored note. Infra loops lean on backtracking and "simulate the search" prompts (dependency/constraint solving, parsing/evaluating, exhaustive validation). If a prompt says "enumerate all valid …" or "place items so constraints hold," name it as backtracking and narrate the prune — the emphasis (per the research) skews toward complete, edge-case-clean implementations, not partial sketches.

Cheat-sheet#

Problem family	Recognition cue	Template variant	Time	Aux space
All subsets / power set	"all subsets"	record every node; start index `i+1`	`O(2^n · n)`	`O(n)`
Subsets with duplicates	subsets + repeats	sort + skip `i>start && a[i]==a[i-1]`	`O(2^n · n)`	`O(n)`
Combinations `nCk`	"choose k of n"	base `size==k`; count-left `break`	`O(C(n,k) · k)`	`O(k)`
Combination Sum (reuse)	target, unlimited reuse	recurse `i`; sorted `break`	exp(`target/min`)	`O(target/min)`
Combination Sum II	target, each once, dups	recurse `i+1`; sort + skip	exp	`O(n)`
Letter combinations	product across positions	fixed map per digit	`O(4^n · n)`	`O(n)`
Permutations	"all orderings"	`used[]` or swap; no start index	`O(n! · n)`	`O(n)`
Permutations w/ dups	orderings + repeats	sort + `!used[i-1]` skip	`O(n! · n)`	`O(n)`
Next permutation	"next arrangement"	pivot → swap → reverse suffix (iterative)	`O(n)`	`O(1)`
Generate parentheses	balanced under a constraint	`open<n`, `close<open` counters	`O(4^n/√n)`	`O(n)`
Word search	spell word on grid path	DFS + mark/un-mark cell	`O(R·C·3^L)`	`O(L)`
N-Queens	non-attacking placement	col / `r−c` / `r+c` sets	`≤ O(n!)`	`O(n)`
Sudoku	fill constrained grid	first-empty cell, try 1–9, undo	`≤ O(9^E)`	`O(1)`
Palindrome partition	split into palindromes	cut points + palindrome prune	`O(2^n · n)`	`O(n)`
Restore IP	split into k valid parts	len 1–3 + leading-zero/≤255 prune	`O(1)`	`O(1)`
Word break / count ways	"can form / how many ways"	recursion + memo on state → DP	`O(n²·L)` memoized	`O(n)`

Two-dial reminder: start-index vs used[] (order-insensitive vs permutation) and i vs i+1 (reuse vs once). Dedup = sort + skip, spelled i>start for subsets/combos, !used[i-1] for permutations.

Self-test#

State the choose → recurse → un-choose invariant in one sentence. What exactly breaks if you skip the un-choose?
Why must you record a copy of the path rather than the path itself? What’s the visible symptom of getting this wrong?
Include/exclude vs start-index subsets — do they emit the same set? Which one generalizes to combinations and combination-sum, and why?
Duplicate handling: why sort first? Explain the different skip conditions for subsets (i>start && a[i]==a[i-1]) and permutations (!used[i-1]).
In Combination Sum vs Combination Sum II, which single change toggles "reuse allowed" vs "each element once," and in which direction?
Give the four steps of the iterative next-permutation algorithm, and the two edge cases (already-largest; trailing duplicates).
In word search, why must you un-mark the cell after the recursive calls? Describe the concrete failure if a shared visited isn’t reset.
In N-Queens, how do r−c and r+c encode the two diagonals, and why does that give O(1) conflict checks?
Generate parentheses uses two guards (open<n, close<open). Prove they guarantee only valid strings are ever built.
State subsets, permutations, and N-Queens complexity, and derive each tree size as branching^depth. What is the easily-forgotten × n factor?
When does memoizing a backtracking recursion help and when does it not? Contrast subsets with word break in one sentence each.
Why is naive fib O(φ^n)? What one line makes it linear, and how does that generalize to top-down DP?
Does the JVM eliminate tail calls? What does Kotlin tailrec do, and what are two ways to handle unbounded recursion depth in Java?
From a cold problem statement, what signals "this is backtracking" rather than DP or greedy? Name at least three cues (constraint size, phrasing, output shape).

Lineage / sources#

Recursion, the base-case/recursive-case decomposition, and the call-stack model are foundational CS (SICP, Abelson & Sussman; CLRS, Introduction to Algorithms). The recursive "leap of faith" framing is from the Berkeley/MIT intro-CS tradition. Backtracking as a named, general technique traces to D. H. Lehmer (1950s) and was formalized/popularized by Robert W. Floyd ("Nondeterministic Algorithms," 1967) and Golomb & Baumert ("Backtrack Programming," 1965); Knuth’s TAOCP Vol. 4A and his Dancing Links (DLX) paper are the canonical deep treatments (exact-cover, N-Queens, Sudoku). Towers of Hanoi is Édouard Lucas (1883); fast exponentiation is ancient (the "Russian peasant"/binary method). The pattern taxonomy and recognition cues (subsets, permutations, combinations, constraint placement) follow Grokking the Coding Interview (DesignGurus/Educative) and the NeetCode 150 backtracking set. Problem numbers reference LeetCode: 17, 22, 31, 37, 39, 40, 46, 47, 51, 52, 77, 78, 79, 90, 93, 131, 139. Interview-format and rubric notes (round mix by level, the "complete, edge-case-clean implementation" bar, the practical/"simulate a search" tilt at infra shops like Snowflake, the four scoring axes) come from Tech Interview Handbook, interviewing.io’s 100K-interview study, and the 2025–26 vendor guides synthesized in the series playbook (00); treat exact round counts and Snowflake specifics as typical-not-guaranteed. The memoization bridge is deliberately a teaser — top-down and bottom-up dynamic programming are the subject of guide 05. For the internals and complexity of every structure used here as a tool — HashMap, HashSet, ArrayList, StringBuilder — see the companion data-structures-java-kotlin-study-guide.md.

Recursion and Backtracking (Java + Kotlin)

The mental model#

1. Recursion fundamentals#

Warm-ups (know these cold — they are the vocabulary)#

2. The backtracking template#

3. Subsets and combinations#

All subsets — two equivalent templates#

Subsets II — duplicates via sort + skip-at-same-level#

Combinations — n choose k (fixed depth + count pruning)#

Combination Sum — reuse vs no-reuse is one character#

Letter combinations of a phone number (LC 17)#

4. Permutations#

All permutations — used[] (LC 46)#

Permutations by in-place swap — O(1) extra state#

Permutations II — duplicates (LC 47)#

Next permutation — the iterative in-place algorithm (LC 31)#

5. Grid and constraint backtracking#

Generate parentheses (LC 22) — counters are the pruning#

Word search (LC 79) — DFS on a grid with mark / un-mark#

N-Queens (LC 51) — one queen per row, O(1) conflict sets#

Sudoku solver (LC 37) — try, recurse, undo on the first empty cell#

Splitting a string — palindrome partitioning (LC 131), restore IP (LC 93)#

6. Pruning, and the bridge to DP#

Pruning is the whole performance story#

The bridge to DP: memoize a backtracking recursion#

7. Stating backtracking complexity cleanly#

Problems & how to solve them#

Interview framing / how to sound senior#

Cheat-sheet#

Self-test#

Lineage / sources#

All permutations — `used[]` (LC 46)#