Backtracking — Eight Problems

1) do an operation → 2) recurse → 3) undo the operation. The analogy from session: you lend a friend ₹500 (step 1), they do the task (step 2 = recursive call), you take the ₹500 back (step 3 = the undo). Step 3 restores state to exactly what it was before step 1.

• Way 1 — explicit undo: index++; recurse; index--. Mutate, recurse, revert.
• Way 2 — pass-forward: recurse with index + 1 directly; no undo needed because you never mutated the caller's state.
• Both are correct. Pick whichever fits. For list/string state (add element, recurse, remove element) you still explicitly undo; for a plain integer index you can usually just pass i + 1.

⭐ TRICK The loop-start rule (biggest transferable insight). Look at the output's 1-D arrays. If every subset/permutation has the same length → start the inner loop at 0 (permutations). If they have variable length → start the loop at start/index and pass i + 1 (or i) forward (subsets, combination sum). This single observation tells you the loop shape before you write any code.

Trigger phrase: "all possible …". "Find all solutions" or "find all combinations" → backtracking. It is brute force over the whole solution space via recursion.

💡 TIP The same template extends to trees and graphs — anything recursion-based. Do operation → recurse into neighbors/children → undo (e.g. mark visited true, recurse, mark visited false). [+] Complexities for these "enumerate everything" problems are inherently exponential — that is expected, not a bug, since the output itself is exponential in size.

Given n pairs of parentheses, generate all well-formed (balanced) combinations. For n = 3 there are 5 results, e.g. ((())), (()()), (())(), ()(()), ()()().

Practice: LeetCode 22 — leetcode.com/problems/generate-parentheses↗

Pattern: Backtracking (constrained string building). Family: generate-all-valid-configurations.

Track counts of open and close brackets; only add a bracket when it keeps the string valid. Final string length is always n * 2 — that's the base case.

• Add '(' only if open < n (can't exceed n opens).
• Add ')' only if close < open (a close needs an unmatched open first).
• Brute force would generate all 2^(2n) strings and validate each — wasteful. The trick prunes invalid branches at construction time.

⭐ TRICK Open gets priority; the guard on closing is close < open, not close < n. A close bracket can never outnumber opens in a valid string, so this one condition guarantees well-formedness — no post-validation needed.

⚠ PITFALL Guarding the close with close < n (mirroring the open guard) lets ) appear before a matching ( and produces invalid strings. The asymmetry is the whole point.

Complexity: Time O(4ⁿ / √n) (nth Catalan number of valid strings, each length 2n). Space O(n) recursion depth. [+] The Catalan bound is the standard tight figure for it.

public List<String> generateParenthesis(int n) {
    List<String> result = new ArrayList<>();
    backtrack(result, "", 0, 0, n);
    return result;
}

// str = current string, open/close = counts so far, n = pairs
private void backtrack(List<String> result, String str, int open, int close, int n) {
    if (str.length() == n * 2) {   // base case: full-length balanced string
        result.add(str);
        return;
    }
    // Way 2: change baked into the recursive call (no explicit undo)
    if (open < n) backtrack(result, str + "(", open + 1, close, n);
    if (close < open)              // key guard: close can't exceed open
    backtrack(result, str + ")", open, close + 1, n);
}

💡 TIP This uses "Way 2" — the + "(" and open + 1 live inside the call, so nothing needs undoing. Strings are immutable in Java, so each branch gets its own copy automatically.

Given an integer array of distinct elements, return all subsets (the power set). No duplicate subsets; any order. For [1,2,3]: [], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3].

Practice: LeetCode 78 — leetcode.com/problems/subsets↗

Pattern: Backtracking (include/exclude via variable-length loop). Family: power-set / combinations.

Every subset is a valid answer, so add the current temp list at every node. Loop from start to end; add element, recurse with i + 1, remove element.

• Return type is List<List<Integer>>; you collect copies of a working "temp" 1-D list.
• Subsets have variable length → loop starts at start, not 0. This is the loop-start rule in action.
• Passing i + 1 (not i) moves strictly forward, so no element repeats within a subset and no subset is generated twice.

⭐ TRICK No Set or visited array needed for dedup. Because the recursion always advances the index (i + 1), each element is considered at most once per path — order is fixed, so combinations never repeat.

⚠ PITFALL When collecting the result, add a copy — new ArrayList<>(temp). Adding temp directly stores a reference that later mutation will corrupt.

Complexity: Time O(n · 2ⁿ) (2ⁿ subsets, O(n) to copy each). Space O(n) recursion depth + output. [+]

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);                 // not required for distinct, but harmless
    backtrack(list, new ArrayList<>(), nums, 0);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> temp, int[] nums, int start) {
    list.add(new ArrayList<>(temp));   // every node is a valid subset
    for (int i = start; i < nums.length; i++) {
        temp.add(nums[i]);             // step 1: do
        backtrack(list, temp, nums, i + 1);   // step 2: recurse (advance index)
        temp.remove(temp.size() - 1);  // step 3: undo
    }
}

💡 TIP [!] The transcript sorts the input here; for the distinct-elements version sorting isn't needed, but it does no harm and keeps the code identical to Subsets II.

Array may contain duplicates; return all unique subsets. For [1,2,2]: [], [1], [1,2], [1,2,2], [2], [2,2].

Practice: LeetCode 90 — leetcode.com/problems/subsets-ii↗

Pattern: Backtracking + sort-and-skip dedup. Family: power-set with duplicates.

Sort first so equal values sit adjacent, then skip a value if it repeats the previous one at the same recursion level. Everything else is identical to Subsets.

• Sort → duplicates become neighbors.
• Skip condition: if (i > start && nums[i] == nums[i-1]) continue;

⭐ TRICK The dedup is i > start, not i > 0. You must allow a duplicate to be used the first time at each level (that's what builds [2,2]), but forbid starting a new branch with the same value twice at the same level (which would rebuild the same subset).

⚠ PITFALL Using i > 0 instead of i > start wrongly kills legitimate [2,2]-style subsets. Also, forgetting to sort makes the adjacency check meaningless.

Complexity: Time O(n · 2ⁿ) worst case; sort adds O(n log n). Space O(n) depth. [+]

Given distinct integers, return all permutations. For [1,2,3]: 6 results — [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1].

Practice: LeetCode 46 — leetcode.com/problems/permutations↗

Pattern: Backtracking with fixed-length output. Family: arrangements / orderings.

Every permutation has the same length (= n), so the loop starts at 0 every time; skip elements already in the temp list. Base case: temp.size() == nums.length → add a copy.

• Fixed length → loop from 0, not from a moving start. Contrast with subsets.
• Guard against reusing an element with if (temp.contains(nums[i])) continue;

⭐ TRICK The loop-start rule again: same-size outputs ⇒ start at 0. This is exactly why permutations loop from 0 while subsets loop from start — the output's shape dictates it.

💡 TIP temp.contains(...) is O(n); for large n a boolean[] used array is faster and is the standard optimization (and is required for Permutations II).

Complexity: Time O(n · n!) (n! permutations, O(n) copy each). Space O(n) depth. [+]

Collection may contain duplicates; return all unique permutations. For [1,1,2]: [1,1,2],[1,2,1],[2,1,1].

Practice: LeetCode 47 — leetcode.com/problems/permutations-ii↗

Pattern: Backtracking + used[] array + sort-and-skip. Family: arrangements with duplicates.

Sort, then use a boolean[] used to track placed indices; skip a duplicate value unless its identical predecessor is already used in the current path.

• Skip condition: if (used[i]) continue; then if (i > 0 && nums[i]==nums[i-1] && !used[i-1]) continue;
• Fixed length ⇒ loop still starts at 0 (it's a permutation).

⭐ TRICK The dedup key is !used[i-1]. If the previous equal value hasn't been used in this path, using the current duplicate first would produce a mirror-image duplicate permutation — so skip it. This enforces that equal values are always consumed left-to-right.

⚠ PITFALL A contains check alone (as in Permutations I) fails here — with duplicate values you must track by index via used[], or you'll wrongly drop valid arrangements. Also: you need both the sort and the !used[i-1] clause; either alone is insufficient.

Complexity: Time O(n · n!) worst case; sort O(n log n). Space O(n) depth + used[]. [+]

Given distinct candidates and a target, return all unique combinations summing to target; each number may be reused unlimited times. For candidates = [2,3,6,7], target = 7: [[2,2,3],[7]]. [+] LC constraints: 1 ≤ candidates.length ≤ 30, unique values, 1 ≤ target ≤ 40.

Practice: LeetCode 39 — leetcode.com/problems/combination-sum↗

Pattern: Backtracking with reuse (stay on same index). Family: combination-sum / unbounded knapsack-style enumeration.

Subtract the chosen candidate from a running remaining; recurse. Two base cases: remaining < 0 → prune; remaining == 0 → record. Combinations are variable-length → loop from start.

• remaining < 0: overshot the target → return without recording.
• remaining == 0: exact hit → add a copy of temp.
• Loan analogy: borrow 100, pay 20, remaining = 80 — keep paying down until it hits 0.

⭐ TRICK Recurse with i, not i + 1. Because a number can be reused unlimited times, you stay on the same index instead of advancing. (This mirrors the "infinite supply of each coin" DP problem.) Still loop from start — never revisit smaller indices — so combinations stay unique.

⚠ PITFALL Passing i + 1 here would forbid reuse and drop valid answers like [2,2,3]. Conversely, looping from 0 instead of start would generate the same combination in different orders (duplicates).

💡 TIP [!] The instructor sorts candidates; sorting isn't required for correctness but enables an early break when nums[i] > remaining (a common pruning follow-up). The "< 150 combinations" line in the statement is just a test-case guarantee — with a dynamic List<List<Integer>> it needs no special handling.

Complexity: Exponential in target/candidate ratio; loosely O(n^(target/min)) nodes. Space O(target/min) depth. [+]

Given an m×n matrix, print all paths from the top-left cell to the bottom-right cell, moving only down or right. For the 3×3 grid [[1,2,3],[4,5,6],[7,8,9]]: paths like 1 2 3 6 9, 1 2 5 6 9, 1 2 5 8 9, 1 4 5 6 9, 1 4 5 8 9, 1 4 7 8 9.

Practice: Not a standard LeetCode problem. GeeksforGeeks — search "Print all possible paths from top left to bottom right of a mXn matrix". Closely related LeetCode: 62 Unique Paths (counts paths) and 797 All Paths From Source to Target (graph analog).

Pattern: Backtracking on a grid; path tracked in a stack/list. Family: grid-path enumeration.

Push current cell → try right, try down (each only if in bounds) → pop current cell. Base case: at the last cell, push it, print the whole path, then pop and return.

• Right move: j + 1 if j + 1 < cols. Down move: i + 1 if i + 1 < rows.
• A stack makes the "push then pop" undo natural, but a plain list works equally well.

⭐ TRICK Add the cell before recursing, remove it after — the classic do/undo on the path container. Because you only move down/right (never up/left), no visited array is needed; you can't revisit a cell within one path.

⚠ PITFALL Bounds-check before each recursive move, and pop the cell after exploring both directions. Forgetting the pop leaks cells from one path into the next.

💡 TIP This generalizes to trees and graphs: same do/recurse/undo, just with children/neighbors instead of down/right, plus a visited set for graphs that can revisit.

Complexity: Number of paths in an m×n grid is C(m+n-2, m-1), each of length m+n-1 to print → exponential output. Space O(m+n) for the path/stack. [+]

public void findPath(int[][] matrix) {
    if (matrix == null || matrix.length == 0) return;
    findPath(matrix, new Stack<Integer>(), 0, 0);
}

private void findPath(int[][] matrix, Stack<Integer> path, int i, int j) {
    int m = matrix.length, n = matrix[0].length;
    if (i == m - 1 && j == n - 1) {          // reached last cell
        path.push(matrix[i][j]);
        System.out.println(path);            // print this complete path
        path.pop();                          // undo before returning
        return;
    }
    path.push(matrix[i][j]);                 // step 1: do
    if (j + 1 < n) findPath(matrix, path, i, j + 1);   // move right
    if (i + 1 < m) findPath(matrix, path, i + 1, j);   // move down
    path.pop();                              // step 3: undo (backtrack)
}

💡 TIP A Stack<Integer> is convenient because push/pop map directly onto do/undo; a List<Integer> with add / remove(size-1) is equivalent.

The one rule that ties them together: read the output's shape. Same-length outputs (permutations) → loop from 0. Variable-length outputs (subsets, combination sum) → loop from start. Reuse allowed → recurse with i; otherwise i + 1. Duplicate inputs → sort, then skip equal neighbors. Everywhere: do → recurse → undo, and store a copy at the base case.

Backtracking — tag: recursion/enumerate-all

• Insight → do op → recurse → undo op. Trigger = "all possible…".
• ⭐ output same length ⇒ loop from 0 · variable length ⇒ loop from start
• ⭐ reuse allowed ⇒ recurse i · else i+1 · dup input ⇒ sort + skip neighbor
• ⚠ store new ArrayList<>(temp) at base case, never the live ref
• doodle: tree of choices, each edge = add elem, dashed edge back = undo

tag: backtracking / string-build · insight: add ')' only when close<open, '(' only when open<n · T O(4ⁿ/√n) S O(n)

bt(s,open,close):
  if s.len==2n: add s; return
  if open<n:   bt(s+"(", open+1, close)
  if close<open: bt(s+")", open, close+1)

⭐ close<open (not close<n)   ·   ⚠ symmetric guard = invalid strings

practice: LeetCode 22 Generate Parentheses

doodle: two counters (o | c), add ')' only if c < o

tag: backtracking / power-set · insight: every node is a subset; advance i+1 · T O(n·2ⁿ) S O(n)

bt(temp,start):
  res.add(copy temp)
  for i=start..n-1:
    add nums[i]; bt(temp,i+1); remove last

⭐ no Set needed (i+1 keeps order fixed)

practice: LeetCode 78 Subsets

doodle: index bar [start→n], pick moves start rightward

tag: backtracking / power-set + dedup · insight: sort, skip equal neighbor at same level · T O(n·2ⁿ) S O(n)

sort(nums)
bt(temp,start):
  res.add(copy temp)
  for i=start..n-1:
    if i>start && nums[i]==nums[i-1]: continue
    add; bt(temp,i+1); remove last

⭐ i>start (not i>0)   ·   ⚠ must sort first

practice: LeetCode 90 Subsets II

doodle: sorted bar, cross out 2nd of equal pair at same start

tag: backtracking / arrangements · insight: fixed length ⇒ loop from 0, skip used · T O(n·n!) S O(n)

bt(temp):
  if temp.size==n: res.add(copy); return
  for i=0..n-1:
    if temp.contains(nums[i]): continue
    add; bt(temp); remove last

⭐ same-size output ⇒ start at 0   ·   💡 boolean[] used faster than contains

practice: LeetCode 46 Permutations

doodle: n slots, fill each from unused pool

tag: backtracking / arrangements + dedup · insight: sort + used[]; skip dup when prev-equal unused · T O(n·n!) S O(n)

sort(nums)
bt(temp,used):
  if temp.size==n: res.add(copy); return
  for i=0..n-1:
    if used[i]: continue
    if i>0 && nums[i]==nums[i-1] && !used[i-1]: continue
    used[i]=T; add; bt(temp,used); used[i]=F; remove last

⭐ skip when !used[i-1]   ·   ⚠ track by index, not contains

practice: LeetCode 47 Permutations II

doodle: sorted slots + used[] checkboxes

tag: backtracking / reuse · insight: subtract from remaining; reuse ⇒ recurse i · T exp S O(target/min)

bt(temp,rem,start):
  if rem<0: return
  if rem==0: res.add(copy); return
  for i=start..n-1:
    add nums[i]; bt(temp,rem-nums[i], i); remove last

⭐ recurse i not i+1 (unlimited reuse)   ·   ⚠ i+1 drops [2,2,3]-type answers

practice: LeetCode 39 Combination Sum

doodle: target counter draining; loop pointer i stays put on reuse

tag: backtracking / grid-path · insight: push cell, try R & D in bounds, pop · T exp S O(m+n)

bt(i,j,path):
  if i==m-1 && j==n-1: push; print; pop; return
  push cell
  if j+1<n: bt(i,j+1,path)   // right
  if i+1<m: bt(i+1,j,path)   // down
  pop cell

⭐ down/right only ⇒ no visited array needed   ·   ⚠ pop after both moves

practice: GfG "all paths top-left to bottom-right m×n matrix" (related: LC 62, LC 797)

doodle: grid, arrows → and ↓ only, from ▢top-left to ▢bottom-right