Topic 9: Backtracking

Key-Intuition: Backtracking solves combinatorial and constraint problems by building candidates incrementally and abandoning invalid partial solutions early.

Canonical Questions #

Permutations and Combinations #

• Generate all permutations or combinations of sets

Problems #

1. Permutations (46)

   We just directly use the path length to determine if the correct length of list has been accumulated (end state) and we just use a set for membership checks. We should also keep track of a sweeping start idx to avoid multiple unnecessary calls. The directionality makes it fast.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

   class Solution: def permute(self, nums: List[int]) -> List[List[int]]: res = [] n = len(nums) def backtrack(path, slot_idx, visited): # end states: if slot_idx == n: res.append(path[:]) for option in nums: if option in visited: continue # can choose this: path.append(option) visited.add(option) backtrack(path, slot_idx + 1, visited) # backtrack on it: path.pop() visited.discard(option) return backtrack([], 0, set()) return res

   Code Snippet 1: Permutations (46)

   We can introduce memory optimisations in the form of in-place swapping of values in the list. The key idea here is to reuse the original array to keep track of “in-consideration” segments within the list. In this particular question, the space-optimisation isn’t really necessary for our solution to be globally competitive.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14

   class Solution: def permute(self, nums: List[int]) -> List[List[int]]: res = [] def backtrack(start): if start == len(nums): res.append(nums[:]) # copy current permutation return # so everything from [0, start] will be the current permutation. for i in range(start, len(nums)): nums[start], nums[i] = nums[i], nums[start] # swap backtrack(start + 1) nums[start], nums[i] = nums[i], nums[start] # backtrack backtrack(0) return res

   Code Snippet 2: Permutations (46) – with memory optimisation (in-place-swapping)
   Pattern Extraction

   Core Insight: At each position, try every unused element. Build the permutation incrementally, backtracking when a position is filled to try the next candidate. Pattern Name: Backtracking with Used-Element Tracking Canonical Section: Backtracking > Permutation and Combination Generation Recognition Signals:

   • “Generate all permutations” of a collection
   • Order matters (\[1,2\] and \[2,1\] are different)
   • All elements must be used exactly once
   • No duplicates in input (for LC 46; LC 47 handles duplicates)

   Anti-Signals:

   • Order doesn’t matter (\[1,2\] and \[2,1\] are same) – that’s combinations, not permutations
   • Elements can be reused – different loop structure (no used tracking)
   • Only need to count permutations, not enumerate – use \(n!\) formula

   Decision Point: Permutations = swap-based or used-set backtracking. Combinations = index-based backtracking with start_idx to avoid re-visiting earlier elements.

   Pitfalls and Misconceptions

   1. Trap: Not making a copy of the path when adding to results. Why: The path list is mutated during backtracking. Without copying, all results point to the same (eventually empty) list. Correction: res.append(path[:]) or res.append(list(path)).
   2. Trap: Using a list for used tracking instead of a set. Why: in on a list is \(O(n)\); on a set it’s \(O(1)\). For permutations of length \(n\), this adds \(O(n)\) per recursive call. Correction: Use a set or boolean array for used tracking.
   Problem Mutations

   1. What if the input has duplicates? (stress-tests: uniqueness assumption) Sort first, then skip duplicates at each decision level: if i > 0 and nums[i] = nums[i-1] and not used[i-1]: continue=. Connects to LC 47 Permutations II.
   2. What if you only needed the next permutation in lexicographic order? (stress-tests: enumeration) Find rightmost ascending pair, swap with the smallest larger element to the right, reverse the suffix. \(O(n)\) per call. Connects to LC 31 Next Permutation.
   3. What if \(n\) were large and you only needed the $k$-th permutation? (stress-tests: generate-all) Use factorial number system: \(k\) divided by \((n-1)!\) gives the first digit, recurse on remainder. \(O(n^2)\) or \(O(n \log n)\) with a Fenwick tree. Connects to LC 60 Permutation Sequence.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Permutations generated via batch canonical enrichment pass. Review against personal solving experience and adjust.
   

2. Permutations II (47) Putting this here because it’s a natural extension to Permutations I above.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

   class Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]: perms = [] nums.sort() visited = set() # idx-es def backtrack(path): # endstates: if len(path) == len(nums): perms.append(path[:]) # gather options: for idx in range(len(nums)): if idx in visited: continue should_ignore = idx > 0 and nums[idx] == nums[idx - 1] and (idx - 1) not in visited if should_ignore: continue # choose this: visited.add(idx) path.append(nums[idx]) backtrack(path) # undo the choice: visited.remove(idx) path.pop() backtrack([]) return perms

   Code Snippet 3: Permutations II, with duplicate handling
   Pattern Extraction

   Core Insight: Sorting reveals duplicate structure; index-order visitation prevents redundant permutation branches by forcing exhaustion of earlier occurrences before later ones.

   Pattern Name: Index-Order Duplicate Skipping (Permutations)

   Canonical Section: Backtracking > Permutations

   Recognition Signals:

   • Sorted array + generate all unique permutations (duplicates explicitly mentioned or implied by constraints)
   • Full n-element permutations required (not k-permutations, not combinations)
   • Output is a list of lists; cardinality is strictly less than n! due to duplicates
   • Problem asks to “avoid duplicate permutations” or gives input with repeated values

   Anti-Signals:

   • Permutations with combinations semantics (k choose n, order doesn’t matter) → use Combinations with Duplicates instead
   • Only counting unique permutations, not generating them → use DP + frequency map + multinomial coefficient
   • Permutations I (no duplicates in input) → standard backtracking without duplicate rule

   Decision Point: The critical discriminator is the duplicate rule itself. Do NOT check “skip if value equals previous value”; check “skip if value equals previous value AND previous index has not been visited.” This forces a total order on which occurrence of a duplicate you explore first. Value-only checks are too aggressive and prune valid permutations.

   Pitfalls and Misconceptions

   1. Trap: Check if idx > 0 and nums[idx] = nums[idx-1]: skip= without also checking whether idx-1 is in the visited set. Why: This skips the second occurrence of a duplicate even when the first has already been placed elsewhere in the permutation, pruning valid branches. Correction: Use if idx > 0 and nums[idx] = nums[idx-1] and (idx-1) not in visited: skip=. Only skip if the earlier index is available, not already used.

   2. Trap: De-duplicate after generating all permutations (e.g., collect all perms, then hashset them). Why: This generates \(O(n! × n log n)\) work instead of O(n! / (product of factorials of duplicate counts)) upfront, defeating the optimization. Correction: Prevent redundant branches at generation time using the index-order rule. Each permutation is generated exactly once.

   3. Trap: Skip duplicates by checking value equality in a frequency map but failing to respect the order in which occurrences are consumed. Why: Without an index-order constraint, you can generate permutation prefixes in any order, leading to duplicates even with frequency tracking. Correction: After sorting, the indices encode the order. Use index-order duplicate skipping, which is deterministic.

   Problem Mutations

   1. What if k < n (k-permutations with duplicates)? Base case changes to len(path) = k=, but the loop and duplicate rule remain unchanged. Generate only k-length permutations with duplicates eliminated. Impact: subset of the full n-permutation results; duplicate rule is more important at small k to avoid near-redundant prefixes.

   2. What if all elements are identical? (e.g., [1, 1, 1, 1]) The duplicate rule becomes maximally aggressive: at each position, you skip all but one index. You generate exactly one permutation: [1, 1, 1, 1]. Impact: correctness check — if your logic fails here, the duplicate rule is broken.

   3. What if input is online (values arrive one at a time)? You cannot sort ahead of time. Switch from index-based tracking to a frequency map: count occurrences of each value, recurse by decrementing counts, backtrack by incrementing. Duplicate rule becomes implicit (you only try each distinct value once per position). Impact: algorithmic family change; index-order skipping is specific to the sorted-array static model.

   4. What if you must output permutations in lexicographically sorted order? If you iterate for idx in range(len(nums)) left-to-right after sorting, output is already in lex order. No algorithm change needed. Impact: verify output format, but algorithm unchanged.

   5. What if you need to count unique permutations instead of generating them? Use the multinomial coefficient formula: n! / (c1! × c2! × ... × ck!), where ci is the count of the i-th distinct value. Backtracking is unnecessary. Impact: complexity drops to O(n) after counting; this is a completely different canonical.

3. Combinations (77)

   This is a good contrast to the permutations solution. We don’t care about the ordering, hence we don’t need a visited set and can just focus on pruning. Combinations is about creating subsets and that ends up being a binary choice for each candidate. Also, complexity wise, the permutations solution runs in factorial time.

   Anyway, the TLDR; is to compare differences in the branch exploration and pruning strategies between the permutations and combinations solutions.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

   class Solution: def combine(self, n: int, k: int) -> list[list[int]]: res = [] def backtrack(start, path): if len(path) == k: res.append(path[:]) return # for every candidate, we either use it or we don't. for i in range(start, n + 1): path.append(i) backtrack(i + 1, path) path.pop() backtrack(1, []) return res

   Code Snippet 4: Combinations (77)

   Interestingly, my own version with the extra pruning step did better compared to the global leetcode performances:

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

   class Solution: def combine(self, n: int, k: int) -> list[list[int]]: res = [] def backtrack(start, k_left, path): if k_left == 0: res.append(path[:]) return # Prune if not enough numbers left to complete combination if (n - start + 1) < k_left: (extra_pruning_backtrack_problem_77) return # Choose the current number path.append(start) backtrack(start + 1, k_left - 1, path) path.pop() # Skip the current number backtrack(start + 1, k_left, path) backtrack(1, k, []) return res

   Code Snippet 5: Combinations (77) – my version, with extra pruning

   It’s mainly from the extra pruning that’s happening (the early returns)

   Pattern Extraction

   Core Insight: Generate all subsets of size \(k\) using backtracking with a start index. Prune when remaining elements can’t fill the required size. Pattern Name: Index-Based Backtracking with Size Constraint Canonical Section: Backtracking > Combination Generation Recognition Signals:

   • “All combinations of \(k\) elements from \([1, n]\)”
   • Order doesn’t matter, no duplicates
   • Size-constrained version of Subsets (LC 78)

   Anti-Signals:

   • Order matters – permutations
   • Elements can be reused – combination sum

   Decision Point: Combinations = subsets + size constraint. The pruning condition (n - i + 1 > k - len(path)=) is the only addition over the subsets template.

   Pitfalls and Misconceptions

   1. Trap: Not pruning when there aren’t enough remaining elements to fill the combination. Why: Without pruning, the backtracking explores branches that can never produce a valid combination. Correction: if n - i + 1 < k - len(path): return (not enough elements left).
   Problem Mutations

   1. What if elements could be reused? (stress-tests: each element once) Don’t advance start index. Connects to LC 39. (notes)
   2. What if \(n\) were very large but \(k\) were small? (stress-tests: moderate \(n\)) The number of combinations is \(\binom{n}{k}\), which is manageable for small \(k\) even with large \(n\).
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Combinations.
   

4. Subsets (78)

   We are asked to find the powerset and are told that there’s no duplicate element in the inputs (all elements are unique).

   See this as having to navigate decision trees with each node (element) having 2 children: choose or no choose. We have a few options on how to implement it:

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

   class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: res = [] def backtrack(i, path): # base case: path is complete when we have no other choices: if i == len(nums): res.append(path.copy()) return backtrack(i + 1, path) # use path that excludes nums[i] path.append(nums[i]) backtrack(i + 1, path) # use path that includes nums[i] path.pop() backtrack(0, []) return res

   Code Snippet 6: Subsets (78) – DFS with include/exlucde branching

   And just as a didactic example, we can also implement this using bitmasking:

   1 2 3 4 5 6 7 8 9 10 11 12

   def subsets(nums): n = len(nums) res = [] # Loop over every possible bitmask (from 0 to 2^n - 1) for mask in range(1 << n): # 1 << n is 2^n subset = [] for i in range(n): if mask & (1 << i): # If the ith bit in mask is set subset.append(nums[i]) res.append(subset) return res

   Code Snippet 7: Subsets (78) – bitmasking approach 🤯
   Pattern Extraction

   Core Insight: At each element, make a binary choice: include it or exclude it. This generates all \(2^n\) subsets. Alternatively, iterate with start_idx to avoid revisiting earlier elements. Pattern Name: Binary Decision Backtracking / Index-Based Subset Generation Canonical Section: Backtracking > Subset Generation Recognition Signals:

   • “Generate all subsets” of a set
   • Order doesn’t matter within subsets
   • No duplicates in input (LC 78) or with duplicates (LC 90)

   Anti-Signals:

   • Permutations needed (order matters) – permutation backtracking
   • Only subsets of a specific size – combinations, add size constraint
   • Elements can be reused – combination sum pattern

   Decision Point: Subsets = include/exclude at each position with start_idx advancing. Permutations = used-set tracking. Combinations = start_idx with size limit.

   Pitfalls and Misconceptions

   1. Trap: Not making a copy of the path when adding to results. Why: The path list is mutated during backtracking. Without copying, all results point to the same (eventually empty) list. Correction: res.append(path[:]) or res.append(list(path)).
   2. Trap: Not advancing start_idx, causing duplicate subsets or infinite recursion. Why: Without start_idx, element 2 can appear before element 1 in a subset, generating duplicates. Correction: Pass i + 1 as the start index for the next recursive call.
   Problem Mutations

   1. What if the input has duplicates? (stress-tests: uniqueness) Sort first, then skip duplicates at each decision level: if i > start and nums[i] = nums[i-1]: continue=. Connects to LC 90 Subsets II.
   2. What if you needed subsets of exactly size \(k\)? (stress-tests: all sizes) Add a size check: only add when len(path) = k=. Prune when len(path) > k. Connects to LC 77 Combinations.
   3. What if elements could be reused? (stress-tests: each element once) Don’t advance start_idx: pass i instead of i + 1. Connects to LC 39 Combination Sum.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Subsets generated via batch canonical enrichment pass.
   

Constraint Satisfaction Problems (CSP) #

• Solve puzzles like N-Queens and Sudoku by pruning invalid states

Problems #

1. ⭐️ N-Queens (51)

   This is a classic backtracking question. We build row by row, and the visited set is compressed by us keeping track of positive and negative diagonals that are already occupied.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

   class Solution: def solveNQueens(self, n: int) -> List[List[str]]: res = [] def build(cols): return [ # using a generator here is useful ''.join('Q' if i == c else '.' for i in range(n)) for c in cols ] def backtrack(row, cols, pos_diag, neg_diag): if row == n: res.append(build(cols)) return for c in range(n): # unsafe positions: if c in cols or (row + c) in pos_diag or (row - c) in neg_diag: continue # use it backtrack( row + 1, cols + [c], pos_diag | {row + c}, neg_diag | {row - c} ) backtrack(0, [], set(), set()) return res

   Code Snippet 8: N-Queens (51) – optimal, succinct solution

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61

   class Solution: def solveNQueens(self, n: int) -> List[List[str]]: # board state management: get_board = lambda: [["."] * n for _ in range(n)] # keep grids, flatten later ans = [] # board state: # emplacing a queen: to mark the cell as "Q" # we need to keep track of boards when we finish it. # path construction (state management): # keep to one changing dimension ==> we will go from top row to bottom row # need to keep track of diagonals from TL to BR and TR to BL (2 types of diagonals) # need to keep track of columns already exploited as well boards = [] def backtrack(row_idx, cols, diagonals_a, diagonals_b, curr_board): if row_idx >= n: # commit the board, create one here: board = get_board() for (r, c) in curr_board: board[r][c] = 'Q' boards.append(["".join(row) for row in board]) return # pick this row, what column? for col_idx in range(n): if col_idx in cols: # taken col continue diagonal_a, diagonal_b = row_idx + col_idx, row_idx - col_idx if diagonal_a in diagonals_a: continue if diagonal_b in diagonals_b: continue # when to commit? # this is an option, we either pick it or we don't: cols.add(col_idx) diagonals_a.add(diagonal_a) diagonals_b.add(diagonal_b) curr_board.add((row_idx, col_idx)) backtrack(row_idx + 1, cols, diagonals_a, diagonals_b, curr_board) # backtrack on it: cols.discard(col_idx) diagonals_a.discard(diagonal_a) diagonals_b.discard(diagonal_b) curr_board.discard((row_idx, col_idx)) return backtrack(0, set(), set(), set(), set()) return boards

   Code Snippet 9: N-Queens (51) – verbose solution

   There’s a bitmasked solution to this as well, which should be seen as a space optimisation:

   1 2 3 4 5 6 7 8 9 10 11 12

   def solveNQueens(n): res = [] def dfs(row, cols, diag1, diag2, path): if row == n: res.append(path[:]) return for c in range(n): if not (cols & (1<<c)) and not (diag1 & (1<<(row+c))) and not (diag2 & (1<<(row-c+n-1))): s = '.'*c + 'Q' + '.'*(n-c-1) dfs(row+1, cols|(1<<c), diag1|(1<<(row+c)), diag2|(1<<(row-c+n-1)), path+[s]) dfs(0, 0, 0, 0, []) return res

   Code Snippet 10: N-Queens (51) – bitmasked space optimisation 🤯

   Here, each int encodes set membership with bits. It’s just the set representation that happens via a single number, which we should see as a space optimisation.

   Pattern Extraction

   Core Insight: Place queens row by row. At each row, try each column; validate against existing queens using column, diagonal, and anti-diagonal conflict sets. Backtrack when no valid column exists. Pattern Name: Constraint-Propagation Backtracking Canonical Section: Backtracking > Constraint Satisfaction Recognition Signals:

   • Place items on a grid satisfying multiple simultaneous constraints
   • Constraints are checkable in \(O(1)\) per placement using auxiliary sets
   • Complete search over configurations (no greedy shortcut)

   Anti-Signals:

   • Only need to count solutions, not enumerate – still backtracking but skip board construction
   • Approximate placement is acceptable – use heuristics (min-conflicts, simulated annealing)

   Decision Point: The \(O(1)\) conflict check using three sets (columns, diagonals row - col, anti-diagonals row + col) is the implementation key. Without this, conflict checking is \(O(n)\) per placement.

   Pitfalls and Misconceptions

   1. Trap: Checking queen conflicts by scanning all previously placed queens (\(O(n)\) per check). Why: With \(n\) rows and up to \(n\) columns per row, this makes the per-node cost \(O(n)\) instead of \(O(1)\). Correction: Use three sets: cols, diags (row - col), anti_diags (row + col). Membership check is \(O(1)\).
   2. Trap: Forgetting to remove from conflict sets when backtracking. Why: Stale entries in the conflict sets block valid placements in sibling branches. Correction: After backtrack(row + 1), remove the queen’s column and diagonals from the sets.
   3. Trap: Using row - col without handling negative values. Why: Python handles negative dictionary keys fine, but in other languages this could cause array index issues. Correction: In Python, row - col can be negative and still works as a set element. In C++/Java, offset by \(n\).
   Problem Mutations

   1. What if you only needed the count of valid placements? (stress-tests: enumeration vs counting) Same backtracking, just increment a counter instead of collecting board configurations. Connects to LC 52 N-Queens II.
   2. What if the board were not square (e.g., \(m \times n\) with \(k\) queens)? (stress-tests: square board) Same constraint-propagation backtracking, but iterate over columns 0 to \(n-1\) and rows 0 to \(m-1\). The number of queens to place becomes a parameter.
   3. What if queens could also attack like knights? (stress-tests: attack pattern) Add knight-move offsets to the conflict check. The constraint set grows but the backtracking structure is identical.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for N-Queens generated via batch canonical enrichment pass. Review against personal solving experience and adjust.
   

2. ⭐️ Sudoku Solver (37)

   For this we just need to be able to have a way to gather the options and the negations properly. Specifically the box-values, which we can get using boxes. The ideal solution just keeps track of all the values that we already see in a preprocessing that is helpful.

   After we do the preprocessing, we attempt to do the backtracking, where one of the end states allows us to shortcircuit and do an early return (if we find the answer). This early return can also be done during the recursive call to backtrack as well!

   Really cool use of the block tracking for the optimal solution.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

   class Solution: def solveSudoku(self, board: List[List[str]]) -> None: """ Do not return anything, modify board in-place instead. """ ROWS, COLS = 9, 9 DIGITS = set("123456789") # now we preprocess to keep track of all the values that we have already seen: empty_slots = [] # visited set across the 3 types of rules to follow rows, cols, boxes = [set() for _ in range(ROWS)], [set() for _ in range(COLS)], [set() for _ in range(ROWS)] for r in range(ROWS): for c in range(COLS): val = board[r][c] if val == '.': empty_slots.append((r, c)) else: rows[r].add(val) cols[c].add(val) box_idx = ((r // 3) * 3) + (c // 3) # lmao, this is great - a 2D to 1D index flattening boxes[box_idx].add(val) # now we figure out how to backtrack: def backtrack(idx=0): # end-state, we aredone: if idx == len(empty_slots): return True r, c = empty_slots[idx] box_idx = ((r // 3) * 3) + (c // 3) # gather options: options = DIGITS - rows[r] - cols[c] - boxes[box_idx] # pick the option: for option in options: board[r][c] = option rows[r].add(option) cols[c].add(option) boxes[box_idx].add(option) # short circuiting return: if backtrack(idx + 1): return True # else reset: board[r][c] = "." rows[r].remove(option) cols[c].remove(option) boxes[box_idx].remove(option) return False backtrack()

   Code Snippet 11: Sudoku Solver (37)
   Pattern Extraction

   Core Insight: Backtracking with constraint propagation. For each empty cell, try digits 1-9, checking row/column/box constraints. Backtrack on conflict. Pattern Name: Constraint Satisfaction Backtracking Canonical Section: Backtracking > Constraint Satisfaction Recognition Signals:

   • Grid with constraints (row, column, box uniqueness)
   • Complete search required (no greedy shortcut)
   • Backtrack on constraint violation

   Anti-Signals:

   • Only validate a Sudoku (not solve) – just check constraints, no backtracking needed
   • Need to count solutions – same backtracking but count instead of return

   Decision Point: \(O(1)\) constraint checking using three sets (rows[r], cols[c], boxes[r//3*3 + c//3]) is the implementation key.

   Pitfalls and Misconceptions

   1. Trap: Checking constraints by scanning the row/column/box each time (\(O(n)\) per check). Why: With 9 constraints checked at each of ~81 cells with up to 9 candidates, the overhead adds up. Correction: Precompute sets of used digits per row, column, and box. \(O(1)\) per check.
   2. Trap: Not backtracking correctly (leaving the digit in the cell after a failed path). Why: After exploring a digit and finding no solution, the cell and constraint sets must be restored. Correction: Remove the digit from the cell and from all constraint sets before trying the next digit.
   Problem Mutations

   1. What if the grid were larger (\(16 \times 16\), \(25 \times 25\))? (stress-tests: \(9 \times 9\)) Same algorithm but exponentially more candidates. Constraint propagation (naked singles, hidden singles) becomes essential for practical performance.
   2. What if you needed all solutions, not just one? (stress-tests: single solution) Don’t return early. Continue backtracking after finding each solution. Count or collect all.
   3. What if some cells had pre-assigned ranges instead of single values? (stress-tests: fixed values) Restrict candidates per cell to the given ranges. Same backtracking structure.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Sudoku Solver.
   

3. Word Search (79)

   Just a DFS style, traverse legal directions.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

   class Solution: def exist(self, board: List[List[str]], word: str) -> bool: ROWS, COLS = len(board), len(board[0]) DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)] n = len(word) # early exit just incase if (ROWS * COLS < n): return False def backtrack(row, col, idx): # endstates: if idx == n: return True # validity checks: if is_invalid:=(not (0 <= row < ROWS and 0 <= col < COLS or not board[row][col] == word[idx]): return False tmp, board[row][col] = board[row][col], "*" # choose from choices: for n_r, n_c in ((row + dr, col + dc) for dr, dc in DIRS): if found:=(backtrack(n_r, n_c, idx + 1)): board[row][col] = tmp return found board[row][col] = tmp return False for r in range(ROWS): for c in range(COLS): if backtrack(r, c, 0): return True return False

   Code Snippet 12: Word Search (79)
   Pattern Extraction

   Core Insight: DFS/backtracking on the grid. For each cell matching the first character, explore all 4 directions recursively. Mark cells as visited during the current path to prevent reuse. Pattern Name: Grid DFS Backtracking for Path Finding Canonical Section: Backtracking > Grid Exploration Recognition Signals:

   • “Find a word in a grid by following adjacent cells”
   • Single word search (for multiple words, use trie: LC 212)
   • Each cell used at most once per path

   Anti-Signals:

   • Multiple words – trie-guided DFS (LC 212)
   • Cells can be reused – no visited tracking needed

   Decision Point: Single word = backtracking DFS per starting cell. Multiple words = trie + backtracking DFS.

   Pitfalls and Misconceptions

   1. Trap: Not restoring visited cells when backtracking. Why: Without restoration, future paths can’t use cells that were on failed paths. Correction: board[r][c] = '#' before recursing, board[r][c] = original after.
   2. Trap: Not short-circuiting when the word is found. Why: Continuing to search after finding the word wastes time. Correction: Return True immediately upon finding a complete match. Propagate True up the recursion.
   Problem Mutations

   1. What if you needed to find multiple words? (stress-tests: single word) Build a trie from all words. Connects to LC 212 Word Search II.
   2. What if cells could be reused? (stress-tests: once per path) Remove visited tracking. Each cell can appear multiple times in the path.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Word Search.
   

Partitioning and Grouping #

• Partition strings or sets into valid groups or palindromic partitions

Problems #

1. Palindrome Partitioning (131)

   we are asked to return the all the palindrome partitions directly. We are checking for cut points and if the region between the cut points is a palindrome or not.

   This is a less performant version because we’re creating explicit sub-strings instead of paying with slice objects.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

   from functools import cache class Solution: def partition(self, s: str): partitions = [] @cache def is_palindrome(left: int, right: int) -> bool: # Checks if s[left:right] is a palindrome return s[left:right] == s[left:right][::-1] def backtrack(start_idx: int, current_partition: list): if start_idx == len(s): partitions.append(list(current_partition)) return for end_idx in range(start_idx + 1, len(s) + 1): if is_palindrome(start_idx, end_idx): current_partition.append(s[start_idx:end_idx]) backtrack(end_idx, current_partition) current_partition.pop() backtrack(0, []) return partitions # =start_idx=: current position in the string to start partitioning # =end_idx=: the (exclusive) end index for the candidate substring # =current_partition=: accumulated list of palindromic substrings for the current path # =partitions=: master list collecting all valid palindrome partitions

   Code Snippet 13: Palindrome Partitioning (131)

   here’s another way that I had written this solution, it’s more performant because we don’t create new strings, just use substring-checks. different comments:

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

   from functools import cache class Solution: def partition(self, s: str): partitions = [] n = len(s) @cache def palindrome(l, r): sub = s[l:r] return sub == sub[::-1] # NOTE: left and right are for use in slicing, so left is inclusive pointer and right is exclusive so when checking for options, right may take the values in range(left + 1, n + 1) def backtrack(left, path): # path is the current partition # end states: if left == n: partitions.append(path[:]) return for right in range(left + 1, n + 1): # because it's right value used in slice syntax (and right is exclusive range) # options are only if it's palindrome if palindrome(left, right): # choose this: path.append(s[left:right]) backtrack(right, path) # don't choose this: path.pop() backtrack(0, []) return partitions

   Code Snippet 14: Palindrome Partitioning (131) – my approach, more performant beacuse uses substring checks without creating new strings
   Pattern Extraction

   Core Insight: Backtracking: at each position, try all possible palindromic prefixes. If the prefix is a palindrome, recurse on the remainder. Collect complete partitions. Pattern Name: Backtracking with Palindrome Prefix Check Canonical Section: Backtracking > Partitioning Problems Recognition Signals:

   • “Partition string into palindromes” and enumerate all valid partitions
   • Each substring must be a palindrome
   • Backtracking over partition points

   Anti-Signals:

   • Minimum number of cuts (not all partitions) – DP. Connects to LC 132

   Decision Point: All partitions = backtracking. Minimum cuts = DP.

   Pitfalls and Misconceptions

   1. Trap: Checking palindromicity with \(O(n)\) string reversal at each call. Why: Repeated checks add \(O(n)\) per candidate substring. Precomputing a palindrome table gives \(O(1)\) per check. Correction: Precompute is_palindrome[i][j] using DP or expand-around-center.
   2. Trap: Not understanding that every string has at least one valid partition (single characters). Why: Single characters are always palindromes. The result is never empty. Correction: This is useful for testing: the “all single characters” partition should always appear.
   Problem Mutations

   1. What if you needed the minimum number of cuts? (stress-tests: enumerate all) DP: dp[i] = min cuts for s[:i]. Connects to LC 132.
   2. What if you needed to count partitions (not enumerate)? (stress-tests: enumerate vs count) Same backtracking structure but count instead of collect. Or DP for counting.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Palindrome Partitioning.
   

2. Combination Sum (39)

   It’s a combination enumeration exercise and backtracking is the first reach approach for this. We then realise that because we’re being asked for ALL the combinations, so it’s brute-force esque and hence backtracking (with some sort of pruning) is our go-to solution.

   This question helps us appreciate how to deal with cases where we can reuse a candidate for an unlimited number of times. The best mental model of this is to think of the decision tree and realise that we can allow semantically different (hence no double counting) but reusable candidates in this path. This allows us to have unique combinations WHILE allowing for duplicate use of an element.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

   class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: res = [] def backtrack(i, path, total): # handle end states: # A: found an ans: if total == target: res.append(path[:]) return # B: exceeds target: if total > target: return for j in range(i, len(candidates)): path.append(candidates[j]) backtrack(j, path, total + candidates[j]) # allow reuse by starting from j again. path.pop() backtrack(0, [], 0) return res # ITERATIVE VERSION: def combinationSum(candidates, target): stack = [([], 0, 0)] res = [] while stack: path, total, start = stack.pop() if total == target: res.append(path) continue if total > target: continue for i in range(start, len(candidates)): stack.append((path + [candidates[i]], total + candidates[i], i)) return res

   Code Snippet 15: Combination Sum (39)

   The stack solution makes it an even more explicit DFS traversal of a decision tree, howewver I think that the backtracking approach is the nicest to write.

   Pattern Extraction

   Core Insight: Like subsets, but elements can be reused (pass i instead of i + 1) and we stop when the running sum reaches or exceeds the target. Pattern Name: Backtracking with Unbounded Element Reuse Canonical Section: Backtracking > Combination Sum Family Recognition Signals:

   • “Find all combinations summing to a target”
   • Elements can be reused unlimited times
   • Order doesn’t matter ([2,3] and [3,2] are the same)

   Anti-Signals:

   • Each element used at most once – advance start_idx. Connects to LC 40
   • Order matters (permutations) – iterate from 0, not start_idx. Connects to LC 377

   Decision Point: Reusable + unordered = pass i with start_idx. Single-use + unordered = pass i + 1. Reusable + ordered = no start_idx.

   Pitfalls and Misconceptions

   1. Trap: Passing i + 1 instead of i, preventing element reuse. Why: i + 1 moves past the current element, enforcing “use at most once.” For reuse, stay at i. Correction: backtrack(i, path + [candidates[i]], remaining - candidates[i]).
   2. Trap: Not sorting and pruning when candidates[i] > remaining. Why: If candidates are sorted and the current one exceeds the remaining target, all subsequent will too. Correction: Sort candidates. In the loop: if candidates[i] > remaining: break.
   Problem Mutations

   1. What if each element could be used at most once? (stress-tests: unlimited reuse) Pass i + 1 instead of i. Also need duplicate-skipping if candidates have duplicates. Connects to LC 40.
   2. What if you needed the count of combinations (not the actual combinations)? (stress-tests: enumeration vs counting) Use DP instead of backtracking: dp[target] + dp[target - candidate]= for each candidate. Much faster. Connects to LC 377.
   3. What if the target were negative and candidates could be negative? (stress-tests: positive-only) No natural pruning (can’t stop when remaining < 0). Need a different bounding strategy or explicit depth limit.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Combination Sum generated via batch canonical enrichment pass.
   

Subset and Sequence Enumeration #

• Enumerate all subsets or restricted sequences with condition checks

Problems #

1. Subsets II (90)

   Compared to the first version Subsets I (78), the input here may have duplicate values. We have to just avoid duplicates, prune correctly and give the right combinations.

   This is what I refer to as “semantically similar” choice in the decision tree. That’s what the lookback duplicate check is all about.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14

   class Solution: def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: result = [] nums.sort() # essential for duplicate handling def backtrack(start, path): result.append(path[:]) for i in range(start, len(nums)): if i > start and nums[i] == nums[i - 1]: # lookback duplicate skip continue path.append(nums[i]) backtrack(i + 1, path) path.pop() backtrack(0, []) return result

   Code Snippet 16: Subsets II (90)

   or this can be a little more expressive of a solution, with more comments:

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

   class Solution: def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: res = [] def backtrack(start_idx, path): # this is a subset, we can add it in # NOTE: we need to avoid duplicate semantic calls as this if start_idx > len(nums): return res.append(path[:]) for choice_idx in range(start_idx, len(nums)): # lookback duplicate check, avoid choosing the same siblings (which would result in the semantically similar choice (and hence duplicate within the result)) if choice_idx > start_idx and nums[choice_idx] == nums[choice_idx - 1]: continue # choose this: path.append(nums[choice_idx]) backtrack(choice_idx + 1, path) #backtrack: path.pop() return nums.sort() # start_idx, path backtrack(0, []) return res

   Code Snippet 17: Subsets II (90)
   Pattern Extraction

   Core Insight: Sort the array first. At each decision level, skip duplicate elements (if i > start and nums[i] = nums[i-1]: continue=). This prevents generating duplicate subsets. Pattern Name: Backtracking with Sorted Duplicate Skipping Canonical Section: Backtracking > Subset Generation (with duplicates) Recognition Signals:

   • “Generate all subsets” with duplicates in input
   • Need unique subsets only
   • Sort + skip pattern

   Anti-Signals:

   • No duplicates in input – standard Subsets (LC 78)

   Decision Point: Duplicates in input = sort + skip. No duplicates = standard backtracking. The sort enables \(O(1)\) duplicate detection via adjacent comparison.

   Pitfalls and Misconceptions

   1. Trap: Not sorting before backtracking. Why: Without sorting, duplicates aren’t adjacent, and the skip condition fails. Correction: nums.sort() before starting backtracking.
   2. Trap: Using if nums[i] = nums[i-1]= without the i > start guard. Why: Without i > start, the first occurrence at each level is also skipped. Correction: if i > start and nums[i] = nums[i-1]: continue=.
   Problem Mutations

   1. What if you needed permutations with duplicates? (stress-tests: subsets vs permutations) Sort + skip with a used boolean array. Skip when not used[i-1] and nums[i] = nums[i-1]=. Connects to LC 47.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Subsets II.
   

2. Letter Combinations of a Phone Number (17)

   We just backtrack, each time is either continue building or not – it’s the classic DFS style backtracking

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

   class Solution: def letterCombinations(self, digits: str) -> List[str]: # early return case, empty input: if not digits: return [] char_to_choices = { "2": list("abc"), "3": list("def"), "4": list("ghi"), "5": list("jkl"), "6": list("mno"), "7": list("pqrs"), "8": list("tuv"), "9": list("wxyz"), } combis = [] def backtrack(path): if len(path) == len(digits): combis.append("".join(path[:])) return choices = char_to_choices[digits[len(path)]] for choice in choices: # choose it: path.append(choice) backtrack(path) # backtrack: path.pop() backtrack([]) return combis

   Code Snippet 18: Letter Combinations of a Phone Number (17)

   I have an alternative BFS-style as well:

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

   class Solution: def letterCombinations(self, digits: str) -> List[str]: if not digits: return [] mapping = { "2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz" } res = [""] for digit in digits: tmp = [] for comb in res: for ch in mapping[digit]: tmp.append(comb + ch) res = tmp return res

   Pattern Extraction

   Core Insight: Each digit maps to 3-4 letters. Backtrack through digits, trying each letter mapped to the current digit. Pattern Name: Backtracking with Fixed Branching Factor Canonical Section: Backtracking > Enumeration Recognition Signals:

   • “All letter combinations” from a phone number
   • Fixed mapping from digits to letters
   • Branching factor = 3 or 4 per digit

   Anti-Signals:

   • Need only the count – just multiply branching factors: \(3^a \cdot 4^b\)

   Decision Point: This is the simplest backtracking problem. Fixed branching, no pruning needed, no duplicate handling.

   Pitfalls and Misconceptions

   1. Trap: Forgetting to handle the empty input case. Why: Empty string should return [] (no combinations), not [''] (one empty combination). Correction: Early return [] if digits is empty.
   Problem Mutations

   1. What if some digits could be pressed multiple times (T9 input)? (stress-tests: single press) Each digit can produce its letter OR the next letter (longer press). More complex branching.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Letter Combinations of a Phone Number.
   

Path and Maze Exploration #

• Explore labyrinths or graphs to find paths from source to target with constraints

Problems #

1. Word Search (79)

   Mentioned earlier, this is really just a DFS style.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

   class Solution: def exist(self, board: List[List[str]], word: str) -> bool: ROWS, COLS = len(board), len(board[0]) def backtrack(r, c, k): if k == len(word): return True if (r < 0 or r >= ROWS or c < 0 or c >= COLS or board[r][c] != word[k]): return False temp, board[r][c] = board[r][c], "#" # mark as visited # careful on the valid direction: for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]: if backtrack(r + dr, c + dc, k + 1): # undo the temp overwrite: board[r][c] = temp return True board[r][c] = temp return False # allow any cell to be a viable start cell: for row in range(ROWS): for col in range(COLS): if backtrack(row, col, 0): return True return False

   Code Snippet 19: Word Search (79)

2. TODO Rat in a Maze (classic) (490) (paid question, alternate link)

3. TODO Unique Paths III (980)

Expression Parsing and Parentheses Generation #

• Generate or validate all valid combinations of parentheses or expressions

  It’s the generation of all that makes us consider a brute-forced (backtracking) approach to these problems.

Problems #

1. Generate Parentheses (22)

   Here, the inputs tell us that we can brute-force because the small range of 1<=n<=8 is hinting at combination finding, which is at most in catalan number complexity. Not much pruning can be done as well

   The idea here is that the path state is kept by keeping track of number of openers and closers we have used. We can only add ( if we have not yet used ALL the opens. We can only add ) if there are more opens than closes so far. These conditions determine our options at each level of the decision tree. We determine end-states by comparing with the total number of entries (2n) as we keep building valid combinations.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

   class Solution: def generateParenthesis(self, n: int) -> List[str]: res = [] TOTAL = n * 2 def backtrack(path, num_open, num_close): # end states: if len(path) == TOTAL: res.append(path) return # choice type 1: if should_add_closer:=(num_close < num_open): backtrack(path + ")", num_open, num_close + 1) # choice type 2: if should_add_opener:=(num_open < n): backtrack(path + "(", num_open + 1, num_close) return backtrack("", 0, 0) return res

   Code Snippet 20: Generate Parentheses (22)
   Pattern Extraction

   Core Insight: Backtracking with two counters: open and close bracket counts. Can add '(' if open count < \(n\). Can add ')' if close count < open count. When both reach \(n\), a valid combination is complete. Pattern Name: Constrained Backtracking with Counter Bounds Canonical Section: Backtracking > Parenthesis Generation Recognition Signals:

   • “Generate all valid combinations of \(n\) pairs of parentheses”
   • Two constraints: can’t exceed \(n\) opens, can’t exceed current opens for closes

   Anti-Signals:

   • Validate parentheses (not generate) – stack or counter
   • Wildcards in parentheses – range tracking (LC 678)

   Decision Point: Generation = backtracking. Validation = stack/counter. The two-counter bound (open < n, close < open) is the core of generation.

   Pitfalls and Misconceptions

   1. Trap: Allowing close brackets before there are open brackets to match.

   Why: close > open means unmatched close brackets, producing invalid strings. Correction: Only add ')' when close < open.

   1. Trap: Not recognising this as a Catalan number problem.

   Why: The number of valid strings is the $n$-th Catalan number. Useful for complexity analysis: \(O(4^n / n^{3/2})\). Correction: Know the count formula but implement via backtracking.

   Problem Mutations

   1. What if you needed the $k$-th valid combination lexicographically? (stress-tests: all combinations)

   Rank-unrank algorithm: count combinations recursively, decide '(' or ')' based on remaining count vs \(k\).

   1. What if there were multiple bracket types? (stress-tests: single type)

   Same backtracking but with more counters and more branching options per position.

   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Generate Parentheses.
   

2. TODO Remove Invalid Parentheses (301)

Combinatorial Optimization with Pruning #

• Search space pruning to optimize or enumerate solutions without brute force. Typically this involves skipping over semantically similar choices in the decision tree. If we take sementically similar choices, that’s how we end up with duplicate combinations.

Problems #

1. Combination Sum II (40)

   Compared to Combination Sum I (39) (ref), this version has possible duplicates within the input numbers (need to deduplicate) and handle

   Here, we first need to know how to handle the deduplication (by sorting it and then by avoiding semantically similar choices in the same layer of the decision tree). Then, we need to focus on how we prune things, also we need to handle duplicates in our input and we do that.

   Once again, the mental model that works for me is “semantically similar choice to be avoided” hence the skipping of duplicates via the lookback that we see below. This is also something we saw earlier for Subsets II (90)

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

   class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: res = [] candidates.sort() # allows me to skip dups for same decision if needed def backtrack(start, path, target): # end states: if target < 0: return if target == 0: res.append(path[:]) return for choice_idx in range(start, len(candidates)): # but don't allow duplicates for THIS choice if is_semantically_duplicate:=(choice_idx > start and candidates[choice_idx] == candidates[choice_idx - 1]): continue # choose it and continue, candidate = candidates[choice_idx] path.append(candidate) backtrack(choice_idx + 1, path, target - candidate) # backtrack on it path.pop() return backtrack(0, [], target) return res

   Code Snippet 21: Combination Sum II (40)
   Pattern Extraction

   Core Insight: Like Combination Sum but each element used at most once. Sort + advance start index + skip duplicates at each decision level. Pattern Name: Backtracking with Single-Use + Duplicate Skipping Canonical Section: Backtracking > Combination Sum Family Recognition Signals:

   • “Find all combinations summing to target, each element at most once”
   • Input may have duplicates (need deduplication)
   • Sort + skip

   Anti-Signals:

   • Elements can be reused – LC 39 (ref) (don’t advance start index)
   • Order matters – LC 377 (no start index)

   Decision Point: Single-use + duplicates = advance start to i + 1 AND skip duplicates: if i > start and candidates[i] = candidates[i-1]: continue=.

   Pitfalls and Misconceptions

   1. Trap: Using i > 0 instead of i > start for the duplicate skip. Why: i > 0 skips the first element at every level, not just duplicates at the same level. Correction: if i > start and candidates[i] = candidates[i-1]: continue=.
   Problem Mutations

   1. What if elements could be reused? (stress-tests: single use) Don’t advance start index. Connects to LC 39. (ref notes)
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Combination Sum II.
   

2. ⭐️ Word Break II (140)

   This is a mix of approaches, it’s somewhat tedius but not difficult to consider if we think calmly and strategise based on the information that we need. For the sentence accumulation, we know that it’s a matter of exploring decision curves (break here as a fork between multiple sentences?…) so it’s a backtracking that we need to do.

   The backtracking can be assisted by a helper DP array or we may directly rely on memoised calls to a backtrack function.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

   # V2: bottom up, dp-assisted from typing import List from functools import cache class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> List[str]: """ This question is a mix of multiple approaches. {preprocessing} 1. we need to know about "segmentability" i.e. can i segment at this location? ==> this is what we can use a DP for 2. need info on where I could have started from given ith idx is the end-segment. ==> need to know valid_starts {gathering the sentences} 1. we start from the right possible index for spaces, then we explore the different approaches and gather a path. this is a decision tree traversal, so it's dfs-like / backtracking that we're doing here """ n = len(s) wordset = set(wordDict) # so dp[i] ==> I can segment at ith idx (for insertion point) dp = [False] * (n + 1) dp[0] = True # vacuous truth # valid starts is going to be a list of lists, it means that ith idx is the end, and keeps track of where we could have started from. valid_starts = [[] for _ in range(n + 1)] for i in range(1, n + 1): # i is the right exclusive idx for slicing, hence goes till i = n for j in range(i): # j is the left inclusive idx for slicing if dp[j] and s[j:i] in wordset: dp[i] = True valid_starts[i].append(j) if not dp[n]: # early returns for can't segment return [] """ After preprocessing, now we can backtrack: """ @cache def backtrack(end): # end states: if end == 0: # i.e. reached the starting idx return [""] sentences = [] for start in valid_starts[end]: word = s[start:end] prefixes = backtrack(start) for prefix in prefixes: if prefix: sentences.append(f"{prefix} {word}") else: # for the empty string case @ terminus (starting idx = end = 0) sentences.append(word) return sentences return backtrack(n)

   Code Snippet 22: Word Break II (140)

   and this is the merely memoised approach:

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

   from functools import cache class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> List[str]: wordSet = set(wordDict) @cache def backtrack(start_idx): # end-cases: if start_idx == len(s): return [""] # trivially, we return a sentence with empty string res = [] # sentences to form starting with start_idx for end in range(start_idx + 1, len(s) + 1): word = s[start_idx:end] if not word in wordSet: continue # we can backtrack now: choices = backtrack(end) for sub in choices: if sub: res.append(f"{word} {sub}") else: # current word is last word res.append(word) # this is the last word in the sentence return res return backtrack(0)

   Pattern Extraction

   Core Insight: DFS/backtracking with memoisation. At each position, try every dictionary word that matches the current prefix. Recurse on the remainder. Collect all valid segmentations. Pattern Name: Backtracking with Memoisation for Enumeration Canonical Section: Backtracking > DP Crossover Recognition Signals:

   • “All valid segmentations” of a string into dictionary words
   • Enumerate all, not just check existence
   • Memoisation prevents re-exploring identical suffixes

   Anti-Signals:

   • Only check existence (boolean) – 1D DP (LC 139)

   Decision Point: Boolean = DP. All segmentations = backtracking with memo. The output type determines the approach.

   Pitfalls and Misconceptions

   1. Trap: Not memoising, causing exponential time on repeated suffix exploration. Why: Without memo, the same suffix is segmented multiple times from different prefixes. Correction: Cache results per start index: memo[start] = list of valid segmentations from start.
   2. Trap: Building strings by concatenation in the recursion (\(O(n)\) per operation). Why: String concatenation creates new objects each time. Correction: Build a list of words, join at the end: ' '.join(words).
   Problem Mutations

   1. What if you only needed the count of segmentations? (stress-tests: enumerate vs count) DP: dp[i] = sum(dp[j] for valid s[j:i]). No backtracking needed.
   2. What if the dictionary were a trie? (stress-tests: set-based) Trie-guided prefix matching during DFS. Can be faster for large dictionaries.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Word Break II.
   

3. TODO Combination Sum IV (377)

Cryptarithm and Puzzle Solving #

• Assign digits or values to letters/variables to satisfy equations or puzzles

Problems #

1. Sudoku Solver (37) – ref here
2. TODO Verbal Arithmetic Puzzle (1307)

Backtracking with Memoization / DP Integration #

• Combine backtracking with caching intermediate results to avoid re-computation

Problems #

1. Word Break (139)

   This is about creating valid segments and there’s a lookup that we would need to do for validity checks. We are asked to find out whether we can segment for this version of the problem.

   The substructure property is as such, if my last segment I can make from the right is legit, and the immediate left of that is also a valid segment then I’m fine with the whole segmentation process. dp[i] keeps track of whether a valid segment ends at ith idx.

   We check out things using 2 pointers, i and j and fill up a 1D dp table for this:

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

   class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: wordSet = set(wordDict) # O(1) lookup n = len(s) dp = [False] * (n + 1) # dp[i] = True if first i characters are segmentable dp[0] = True # empty substring is segmentable max_word_length = max(map(len, wordDict)) if wordDict else 0 for i in range(1, n + 1): # Limit left boundary (j) to speed up checks (optimization) for j in range(max(0, i - max_word_length), i): if dp[j] and s[j:i] in wordSet: dp[i] = True break # early break for efficiency, since we know that dp[i] is already a legit segmentation. return dp[n]

   Code Snippet 23: Word Break (139)
   Pattern Extraction

   Core Insight: dp[i] = True if s[:i] can be segmented into dictionary words. For each \(i\), check all \(j < i\): if dp[j] is True and s[j:i] is in the dictionary, then dp[i] is True. Pattern Name: 1D DP on String Segmentability Canonical Section: 1D DP > Word Segmentation / Backtracking > DP Crossover Recognition Signals:

   • “Can the string be segmented into dictionary words?”
   • Boolean output (segmentability)
   • Overlapping subproblems (same prefixes checked multiple times)

   Anti-Signals:

   • Need all valid segmentations, not just existence – backtracking/DFS. Connects to LC 140
   • Dictionary is a trie and you need pattern matching – trie-based segmentation

   Decision Point: Boolean segmentability = 1D DP. All segmentations = backtracking with memoisation.

   Pitfalls and Misconceptions

   1. Trap: Using pure backtracking without memoisation. Why: Exponential time due to overlapping subproblems. Correction: Use DP: dp[i] = any(dp[j] and s[j:i] in wordDict for j in range(i)).
   2. Trap: Not initialising dp[0] = True. Why: The empty prefix is trivially segmentable. Without this base case, no position can ever become True. Correction: dp[0] = True.
   3. Trap: Checking all substrings when only dictionary-length substrings are valid. Why: If the longest word has length \(L\), only check j in range(max(0, i - L), i). Correction: Track max_word_len and limit the inner loop.
   Problem Mutations

   1. What if you needed all valid segmentations? (stress-tests: boolean vs enumeration) DFS/backtracking with memoisation. Connects to LC 140 Word Break II.
   2. What if the dictionary were very large and strings were long? (stress-tests: dictionary size) Use a trie for the dictionary to speed up prefix matching.
   3. What if you needed the minimum number of words to segment the string? (stress-tests: boolean vs optimisation) Change DP to track min count: dp[i] = min(dp[j] + 1) for valid s[j:i]. Same structure, different aggregation.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Word Break generated via batch canonical enrichment pass.
   

2. Target Sum (494)

   We can solve this using a recursive brute-force (backtracking) approach, or we can rephrase the question into one that is a bounded knapsack problem where the LHS = RHS. The input constraints suggest this.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

   # M1: Recursive solution: from functools import cache class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: @cache def helper(idx, target): if idx == 0: a, b = nums[idx], -nums[idx] # trivial edge case when target = 0 then both will work and that's 2 wayss if a == target and b == target: return 2 return 1 if a == target or b == target else 0 num = nums[idx] # use this number, explore both cases, when it's a positive number and when its a negative number: pos_ways, neg_ways = helper(idx - 1, target + num), helper(idx - 1, target - num) return pos_ways + neg_ways return helper(len(nums) - 1, target)

   Code Snippet 24: Target Sum (494)

   For the bounded knapsack framing of this problem, there are 3 things to take note:

   1. the way we convert it into a bounded knapsack problem,
   2. the problem being a combination sum problem, therefore we have to iterate over the options to avoid double counting and
   3. the order of traversal of the range (right to left).

      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

      # M2: Iterative bottom up with space optimisation (1D array rollup that allows us to reduce space usage) class Solution: def findTargetSumWays(self, nums: List[int], target: int) -> int: # rephrasing the problem into a bounded knapsack problem. # we want to have LHS = RHS the target will also be split num_sum = sum(nums) total = (num_sum + target) if is_impossible:=(num_sum < abs(target) or total % 2 != 0): return 0 knap_target = total // 2 # we want to select subset such that we will reach knap_target. # dp[i] = num ways to reach target val = i dp = [0] * (knap_target + 1) # to allow for 1-indexed dp[0] = 1 # NOTE [1]: we wanna find the number of combis here, so we control the order of inclusion of nums so that we don't end up doing permutation_sum type and end up with double counting for num in nums: # NOTE [2]: the order here matters and we need to go from right to left (big to small) to avoid double counting. # for target_sum in range(num, knap_target + 1): # so this will be wrong for target_sum in range(knap_target, num - 1, -1): gap = target_sum - num dp[target_sum] += dp[gap] return dp[knap_target]

   Pattern Extraction

   Core Insight: Reframe as: find a subset \(P\) (assigned +) and subset \(N\) (assigned -) such that \(P - N = \text{target}\) and \(P + N = \text{sum}\). So \(P = (\text{target} + \text{sum}) / 2\). This converts to a 0/1 knapsack subset sum problem. Pattern Name: Target Sum to Subset Sum Reduction (0/1 Knapsack) Canonical Section: 1D DP > 0/1 Knapsack Recognition Signals:

   • “Assign + or - to each element to reach target”
   • Binary choice per element (include in P or N)
   • Reduction to subset sum

   Anti-Signals:

   • Elements can be reused – unbounded knapsack
   • Order matters – different DP structure

   Decision Point: The algebraic reframing (\(P = (\text{target} + \text{sum}) / 2\)) converts a \(2^n\) brute force into an \(O(n \cdot P)\) DP. This reduction is the key insight. Interviewer Comms: “I reframe: let \(P\) be the sum of elements assigned +. Then \(P = (\text{total} + \text{target}) / 2\). If this isn’t an integer, answer is 0. Otherwise it’s a counting knapsack: how many subsets sum to \(P\)? I use 1D DP with backward iteration (0/1 knapsack).”

   Pitfalls and Misconceptions

   1. Trap: Not recognising the subset sum reduction. Why: Without the reduction, the only approach is \(2^n\) brute force or 2D DP with \(\text{sum}\) as a dimension. Correction: Derive: \(P + N = \text{sum}\), \(P - N = \text{target}\), so \(P = (\text{sum} + \text{target}) / 2\).
   2. Trap: Forgetting the feasibility checks. Why: If \((\text{sum} + \text{target})\) is odd or \(\text{target} > \text{sum}\) (absolute value), no solution exists. Correction: Check if (total + target) % 2 ! 0 or abs(target) > total: return 0=.
   3. Trap: Using forward iteration (unbounded knapsack) instead of backward (0/1 knapsack). Why: Forward iteration allows reusing elements. Each element should be used exactly once. Correction: Iterate the DP array backward: for j in range(P, num - 1, -1): dp[j] + dp[j - num]=.
   Problem Mutations

   1. What if elements could be reused? (stress-tests: each element once) Forward iteration (unbounded knapsack). Same DP, different loop direction.
   2. What if you needed the actual assignments, not just the count? (stress-tests: count vs enumerate) Backtracking or augment DP with parent tracking for reconstruction.
   3. What if values were large but count was small (\(n \leq 20\))? (stress-tests: value-based DP) Meet-in-the-middle: split into two halves, enumerate \(2^{n/2}\) sums each, use a hash map. \(O(2^{n/2})\).
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Target Sum.
   

SOE #

• Forgetting to backtrack (undo changes) causing state corruption. Please handle the state resets correctly.

• Inefficient or no pruning leading to exponential runtime. Backtracking is already a brute-forcing approach. Just thinking about the end states should give intuition about how to prune cleverly.

• string questions: just use python approach of [open, close) ranges, that’s the simplest to reason with in my opinion.

• NOT finding an easy way to deduplicate (e.g. by sorting the inputs then skipping the duplicates based on previous value.)

• Missing base case or terminal condition resulting in infinite recursion

• NOT COPYING a current snapshot, which leads to mutable objects being shared around. e.g. the powerset (subset) problem, in the base case / ending case we need to copy over the currently accumulating path

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

  class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: res = [] def backtrack(i, path): # base case: path is complete when we have no other choices: if i == len(nums): res.append(path.copy()) # NOTE: this is the copy over point return backtrack(i + 1, path) # use path that excludes nums[i] path.append(nums[i]) backtrack(i + 1, path) # use path that includes nums[i] path.pop() backtrack(0, []) return res

• Attempting to copy over set based or tuple hacking versions. Using these set based approaches will never be good enough for the usual expected space constraints.

• Backtracking careful: careful on the use of the correct pointers when doing the recursive call to backtrack. I accidentally used start_idx + 1 instead of choice_idx + 1 and was dumbfounded.

Decision Flow #

• Enumerate ALL valid configurations? -> Backtracking with pruning
• Enumerate ALL permutations or combinations? -> Backtracking with swap-based or index-based generation
• Constraint satisfaction (Sudoku, N-Queens)? -> Backtracking with constraint propagation
• Can solutions be built incrementally with validity checks at each step? -> Backtracking. If not (validity only checkable at completion), consider brute force with filtering.
• Is the search space a tree (choices branch, no revisiting)? -> Standard backtracking. Is it a graph (revisiting possible)? -> Add visited tracking.
• Optimisation over all configurations? -> If greedy choice property holds, use greedy. If optimal substructure, use DP. Backtracking is the fallback when neither applies.

Styles, Tricks and Boilerplate #

Styles #

• when using a recursive approach, the boundary checks should always be first before accessing the board cell

• prefer NOT to use genexprs for grid movement candidate enumeration, both for readability and speed performance of the code

  positive and negative example

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

  class Solution: def exist(self, board: List[List[str]], word: str) -> bool: ROWS, COLS = len(board), len(board[0]) DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)] n = len(word) # early exit just incase if (ROWS * COLS < n): return False def backtrack(row, col, idx): # endstates: if idx == n: return True # validity checks: if is_invalid:=(not (0 <= row < ROWS and 0 <= col < COLS) or not board[row][col] == word[idx]): return False tmp, board[row][col] = board[row][col], "*" # choose from choices: for n_r, n_c in ((row + dr, col + dc) for dr, dc in DIRS): if found:=(backtrack(n_r, n_c, idx + 1)): board[row][col] = tmp return found board[row][col] = tmp return False for r in range(ROWS): for c in range(COLS): if backtrack(r, c, 0): return True return False

  Code Snippet 25: negative example: don't use the genexps for candidates

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

  class Solution: def exist(self, board: List[List[str]], word: str) -> bool: ROWS, COLS = len(board), len(board[0]) def backtrack(r, c, k): if k == len(word): return True if (r < 0 or r >= ROWS or c < 0 or c >= COLS or board[r][c] != word[k]): return False temp, board[r][c] = board[r][c], "#" # mark as visited # careful on the valid direction: for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]: if backtrack(r + dr, c + dc, k + 1): # undo the temp overwrite: board[r][c] = temp return True board[r][c] = temp return False # allow any cell to be a viable start cell: for row in range(ROWS): for col in range(COLS): if backtrack(row, col, 0): return True return False

  Code Snippet 26: positive example