Topic 9: Backtracking

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

Canonical Question Types #

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

   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

2. 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

   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: 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

3. 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 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

   # DFS WITH INCLUDE/EXCLUDE BRANCHING 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 # BITMASKING AS A DIDACTIC IMPLEMENTATION 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

   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 13 14

   # BITMASKING AS A DIDACTIC IMPLEMENTATION 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

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 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 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91

   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 # or more verbosely written: 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

   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

   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.

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!

   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()

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

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

   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

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

   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.

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

   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

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

   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

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

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

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), 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

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)

   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)

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)

   Really cool use of the block tracking. 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.

   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

   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") empty_slots = [] rows, cols, boxes = [set() for _ in range(ROWS)], [set() for _ in range(COLS)], [set() for _ in range(ROWS)] # now we preprocess: 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()

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]

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)

   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]

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 #

• Need all valid configurations? → Backtracking
• Heavy constraints combined with small input size? → Backtracking + pruning
• Enumerate subsets or permutations? → Backtracking with state arrays

Style, Tricks, Boilerplate #

Style #

• in a recursive approach, the boundary checks should always be first before accessing the board cell
• don’t use genexprs for grid movement candidate enumeration, both for readability and speed performance of the code

  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 62 63 64 65 66 67 68

  # POSITIVE DEMO: 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 # NEGATIVE DEMO 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

Boilerplate #

• Backtracking boilerplate:

  The comments here show the first few things to think about when implementing the backtrack:

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

  class Solution: def generateParenthesis(self, n: int) -> List[str]: res = [] TOTAL = n * 2 def backtrack(path, num_open, num_close): # end states: these are the ways in which we can prune the exploration tree. 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) # optional: if the path is mutated, then we might want to undo the changes. # choice type 2: if should_add_opener:=(num_open < n): backtrack(path + "(", num_open + 1, num_close) return backtrack("", 0, 0) return res

Tricks #

1. accuracy trick for sudoku problems: Block calculations for sudoku grid blocks

   1. have to multiply the thing by 3 as well, so it’s idx = (block_idx) * num_blocks and this gives

      1 2	block_row_start, block_col_start = (row // 3) * 3, (col // 3) * 3 block_vals = {board[r][c] for r in range(block_row_start, block_row_start + 3) for c in range(block_col_start, block_col_start + 3) if board[r][c] != "."}

      or even better, look at the trick used in the optimal solution, were we flatten it into a single dimension: get_box_idx = lambda r,c: (r//3) * 3 + (c//3)

      this is referring to the sudoku solver problem

      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

      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") empty_slots = [] rows, cols, boxes = [set() for _ in range(ROWS)], [set() for _ in range(COLS)], [set() for _ in range(ROWS)] # now we preprocess: 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()

2. Diagonals / Slope Trick: straight up y = mx + c, use c to uniquely identify a slope

   • A diagonal for a particular cell can be represented via a single integer!

     we can capture diagonals using a set of integers, because we just need to define the “slope”. The idea here is actually similar to how we take y = mx + c. m is always 1 for us for both the diagonals so imagine it’s just y = x + c. We just use the C to compare diagonals.

     c = y + x (positive diagonal)

     and if it’s negative diagonal then it’s c = y - x

     Check out the learnings within “N-Queens” problem.