Backtracking

Problem: Given distinct integers, return every possible subset (the power set), in any order.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ nums.length ≤ 10 · -10 ≤ nums[i] ≤ 10 · All the numbers of nums are unique.

From brute force to the pattern: There are 2ⁿ subsets, so any solution is at least O(n · 2ⁿ) to output them. Backtracking (or iterating over bitmasks) generates each subset exactly once without duplicates.

Spot it: "all possible subsets" plus n ≤ 10. The output alone has 2ⁿ items, so exponential time is unavoidable and expected.

Key insight: Each element gives a yes/no decision: take it or skip it. That's a binary decision tree of depth n with 2ⁿ leaves, and each leaf is one subset. The first visualizer above draws exactly this tree.

Approach (step by step):

1. backtrack(index) decides about nums[index]. The path so far holds the chosen numbers.
2. If index == len(nums), every number has been decided, so record a copy of path.
3. Take branch: path.append(nums[index]), recurse with backtrack(index + 1), then path.pop() to undo.
4. Skip branch: recurse with backtrack(index + 1) without adding anything.
5. Start with backtrack(0) and return results.

from typing import List

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        self.nums = nums
        self.path = []          # numbers chosen so far on the current branch
        self.results = []       # every finished subset
        self.backtrack(0)
        return self.results

    def backtrack(self, index):
        # 'index' = which number we are deciding about right now (take it or skip it)
        if index == len(self.nums):
            # decided about every number: this branch is a leaf, save a COPY of path
            self.results.append(self.path[:])
            return
        # Branch 1: take nums[index]
        self.path.append(self.nums[index])
        self.backtrack(index + 1)
        self.path.pop()         # undo the take before trying the other branch
        # Branch 2: skip nums[index] (path is unchanged)
        self.backtrack(index + 1)

What the code is doing, line by line:

1. subsets stores the input and two lists on self so the helper method can reach them: path (numbers taken on the current branch) and results (finished subsets). Then it starts the decision tree at index = 0.
2. backtrack(index) makes one yes/no decision about nums[index].
3. If index == len(self.nums) every number has been decided, so this is a leaf: save self.path[:] (a copy) and return.
4. Branch 1 (take): append the number, recurse to the next index, then pop it so the path is clean again.
5. Branch 2 (skip): recurse to the next index without adding anything.
6. Each number doubles the number of branches, so 3 numbers give 2 × 2 × 2 = 8 leaves = 8 subsets.

Dry run on the example:

Edge cases to test:

• An empty array → [[]].
• A single element → [[], [x]].
• Negative numbers (they don't matter).

Complexity: O(n·2ⁿ) time (2ⁿ subsets, each copied in O(n)), O(n) recursion depth.

Problem: Return every ordering of a list of distinct integers.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ nums.length ≤ 6 · -10 ≤ nums[i] ≤ 10 · All the integers of nums are unique.

From brute force to the pattern: There are n! permutations, so the output alone is O(n · n!). Backtracking with a used array produces each permutation once.

Spot it: "all possible permutations". Order matters, so [1,2] and [2,1] both count. A start index would lose orderings. Use used flags.

Key insight: At depth d you pick which unused number goes in position d. That gives n choices, then n−1, then n−2… for n! leaves. The second visualizer above shows the tree growing.

Approach (step by step):

1. Keep path and a used flag per index.
2. If path is as long as nums, record a copy.
3. Loop over all indices (order matters, so there's no start) and skip those already used.
4. Choose: mark used + append. Explore: recurse.
5. Un-choose: pop and unmark. Undo both changes.

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        self.nums = nums
        self.path = []                      # the ordering built so far
        self.results = []                   # every complete ordering
        self.used = [False] * len(nums)     # used[i] is True while nums[i] is in path
        self.backtrack()
        return self.results

    def backtrack(self):
        if len(self.path) == len(self.nums):
            # every number has a position: save a COPY of this ordering
            self.results.append(self.path[:])
            return
        # order matters, so look at EVERY index (no 'start')
        for i in range(len(self.nums)):
            if self.used[i]:
                continue                    # already placed earlier in this path
            number = self.nums[i]
            self.used[i] = True             # choose: mark it used...
            self.path.append(number)        # ...and put it in the next position
            self.backtrack()                # explore
            self.path.pop()                 # un-choose: undo BOTH changes
            self.used[i] = False

What the code is doing, line by line:

1. permute sets up path, results and a used list of False flags ([False] * n makes a list of n copies of False), then starts the search.
2. backtrack() fills the next free position. When path is as long as nums, the ordering is complete, so a copy is saved.
3. The loop looks at every index from 0, because a number further left may still go into a later position. Indices already used on this path are skipped.
4. Choosing changes two things: the flag used[i] = True and path.append. After the recursive call returns, both are undone in reverse order so the next loop iteration starts clean.

Dry run on the example:

Edge cases to test:

• A single element.
• Negative numbers.
• (All numbers are distinct here; with duplicates see Permutations II.)

Complexity: O(n·n!) time, O(n) extra space.

Problem: Given distinct positive candidates and a target, list every unique combination that sums to target. You may reuse a number any number of times.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ candidates.length ≤ 30 · 2 ≤ candidates[i] ≤ 40 · All elements of candidates are distinct. · 1 ≤ target ≤ 40

From brute force to the pattern: Generating all sequences up to the target and de-duplicating is wasteful. Choosing in non-decreasing index order avoids duplicates, and pruning on a negative remainder (faster after sorting) cuts dead branches early.

Spot it: "all unique combinations" + "sum to target". Combinations (order doesn't matter), so use start. Reuse is allowed, so recurse with i, not i+1.

Key insight: Track the remaining amount. Sort first: the moment a candidate exceeds the remainder, every later one does too, so you can break. That's powerful pruning.

Approach (step by step):

1. Sort the candidates so you can stop early.
2. backtrack(start, remaining): if remaining == 0, record a copy of the path.
3. Loop i from start. If candidates[i] > remaining, break: every later candidate is bigger still.
4. Append the candidate and recurse with backtrack(i, remaining − number). Passing i (not i+1) allows reuse.
5. Pop to undo.

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()           # sorted, so we can stop as soon as a number is too big
        self.candidates = candidates
        self.path = []              # numbers picked so far
        self.results = []           # combinations that hit the target exactly
        self.backtrack(0, target)
        return self.results

    def backtrack(self, start, remaining):
        # 'remaining' = how much we still need to add to reach the target
        if remaining == 0:
            self.results.append(self.path[:])   # exact hit: save a COPY
            return
        for i in range(start, len(self.candidates)):
            number = self.candidates[i]
            if number > remaining:
                break               # sorted: this and every later number is too big
            self.path.append(number)            # choose
            self.backtrack(i, remaining - number)   # explore; i (not i + 1): reuse allowed
            self.path.pop()                     # un-choose

What the code is doing, line by line:

1. Sort the candidates, store them on self, and start with the full target still remaining.
2. If remaining == 0 the path sums exactly to the target, so a copy is saved.
3. The loop starts at start, so we never go back to smaller indices. That is what keeps [2,3] and [3,2] from both appearing.
4. Because the list is sorted, the first number > remaining means all later ones are too big as well, so we break out of the loop instead of just skipping one.
5. We recurse with i (not i + 1), so the same number can be picked again, and with remaining - number because we just used up that much. Then pop undoes the choice.

Dry run on the example:

Edge cases to test:

• No combination exists → [].
• A candidate equal to the target.
• A target smaller than every candidate.

Complexity: exponential, roughly O(N^(T/m)) where T = target and m = smallest candidate. Recursion depth is at most T/m.

Problem: Place n queens on an n × n board so that no two share a row, column or diagonal. Return every such board.

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 9

From brute force to the pattern: Trying every placement of n queens on n² squares is astronomically large. One queen per row with O(1) column/diagonal checks prunes almost everything: about O(n!).

Spot it: "return all distinct solutions" + placement constraints. That's classic constraint-satisfaction backtracking.

Key insight: Put exactly one queen per row, so the row is the depth of the tree. For O(1) conflict checks, keep three sets: used columns, used diagonals (r − c is constant along ↘), and used anti-diagonals (r + c is constant along ↙).

Approach (step by step):

1. Place exactly one queen per row and recurse row by row, so the row is the depth.
2. Keep three sets: used columns, used row − col (↘ diagonals) and used row + col (↙ anti-diagonals).
3. In row row, try every column col. Skip it if any set already contains its key (attacked → prune).
4. Place the queen: add to all three sets, remember the column, recurse to row + 1.
5. Remove the queen from all three sets (un-choose) and try the next column.
6. When row == n, build the board strings from the remembered columns and record them.

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        self.n = n
        self.results = []
        self.queen_col = [-1] * n       # queen_col[row] = column of the queen in that row (-1 = none yet)
        self.used_columns = set()       # columns that already hold a queen
        self.used_diagonals = set()     # row - col is the same along a down-right diagonal
        self.used_anti_diagonals = set()    # row + col is the same along a down-left diagonal
        self.backtrack(0)
        return self.results

    def backtrack(self, row):
        if row == self.n:
            # a queen sits in every row: turn the columns into board strings
            board = []
            for r in range(self.n):         # r = row number
                col = self.queen_col[r]
                row_text = "." * col + "Q" + "." * (self.n - col - 1)
                board.append(row_text)
            self.results.append(board)
            return
        for col in range(self.n):           # try every column in this row
            diagonal = row - col
            anti_diagonal = row + col
            if col in self.used_columns:
                continue                    # attacked from above in the same column
            if diagonal in self.used_diagonals or anti_diagonal in self.used_anti_diagonals:
                continue                    # attacked along a diagonal
            # choose: place the queen and remember everything it attacks
            self.used_columns.add(col)
            self.used_diagonals.add(diagonal)
            self.used_anti_diagonals.add(anti_diagonal)
            self.queen_col[row] = col
            self.backtrack(row + 1)         # explore the next row
            # un-choose: lift the queen so the next column can be tried
            self.used_columns.remove(col)
            self.used_diagonals.remove(diagonal)
            self.used_anti_diagonals.remove(anti_diagonal)
            self.queen_col[row] = -1

What the code is doing, line by line:

1. solveNQueens prepares queen_col (one slot per row, -1 = empty) and three sets that answer "is this square attacked?" instantly: used columns, used row - col diagonals and used row + col anti-diagonals.
2. backtrack(row) places the queen for one row. If row == n, every row has a queen, so we build the board: for each row, col dots, a Q, then the remaining dots.
3. Otherwise we try every column. A column is skipped when it, its diagonal, or its anti-diagonal is already in a set: that square is attacked, so the whole subtree below it is pruned.
4. To place the queen we add its three keys to the sets and record its column, then recurse to row + 1.
5. When the call returns we remove exactly those three keys and reset queen_col[row], so the board is as it was before and the next column can be tried.

Dry run on the example:

(Traced on n = 4 until the first solution; the search continues the same way and finds the mirror-image board too.)

Edge cases to test:

• n = 1 → one board.
• n = 2 or n = 3 → no solutions.
• Building the output strings correctly.

Complexity: O(n!) time in the worst case (far less in practice thanks to pruning), O(n) space for the sets and recursion. n = 8 has 92 solutions.

Problem: Given a letter grid and a word, return whether the word can be traced through 4-directionally adjacent cells, using each cell at most once.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: m == board.length · n = board[i].length · 1 ≤ m, n ≤ 6 · 1 ≤ word.length ≤ 15 · board and word consists of only lowercase and uppercase English letters.

From brute force to the pattern: Trying every path in the grid is exponential no matter what, but backtracking prunes as soon as a letter doesn't match: O(r · c · 3^L).

Spot it: it looks like grid traversal, but "each cell at most once per path" means a cell used by one attempt must be available again to the next attempt. So you must un-mark it when you back out. That's backtracking.

Key insight: DFS from each cell with index k into the word. Mark the cell with '#' while it's on the current path and restore it afterwards. Return early on the first success.

Approach (step by step):

1. Try every cell as the starting point of the word.
2. dfs(row, col, index): if index == len(word), every letter matched, so return True.
3. If (row, col) is out of bounds or its letter isn't word[index], return False.
4. Choose: overwrite the cell with '#' so this path can't reuse it, then try the 4 neighbors with index + 1.
5. Un-choose: restore the original letter (even on success), then return the result.

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        self.board = board
        self.word = word
        self.rows = len(board)
        self.cols = len(board[0])
        # the 4 neighbours as [row change, column change]: down, up, right, left
        self.directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        # try every cell as the place where the word starts
        for row in range(self.rows):
            for col in range(self.cols):
                if self.dfs(row, col, 0):
                    return True
        return False

    def dfs(self, row, col, index):
        # 'index' = which letter of the word this cell must match
        if index == len(self.word):
            return True                     # matched every letter
        if row < 0 or row >= self.rows or col < 0 or col >= self.cols:
            return False                    # stepped off the board
        if self.board[row][col] != self.word[index]:
            return False                    # wrong letter (a cell on this path holds '#')
        saved_letter = self.board[row][col]
        self.board[row][col] = "#"          # choose: occupy this cell for the current path
        found = False
        for direction in self.directions:
            next_row = row + direction[0]
            next_col = col + direction[1]
            if self.dfs(next_row, next_col, index + 1):
                found = True
                break                       # one success is enough
        self.board[row][col] = saved_letter     # un-choose: free the cell again (even on success)
        return found

What the code is doing, line by line:

1. exist stores the board, the word and the board size on self, lists the four neighbour directions, and tries every cell as a starting point. The first success returns True.
2. dfs(row, col, index) asks: can the word, from letter index onward, be traced starting at this cell?
3. If index == len(word), all letters were matched by earlier cells, so the answer is True.
4. If the cell is off the board, or holds a different letter, this path fails. A cell marked '#' never equals a letter, so a path can't reuse its own cells.
5. Choose: remember the letter and overwrite the cell with '#'. Explore: try the four neighbours with index + 1, stopping at the first success.
6. Un-choose: put the letter back no matter what, so other starting points and other paths can use this cell.

Dry run on the example:

(Board ABCE / SFCS / ADEE, word "ABCCED".)

Edge cases to test:

• The word is longer than the number of cells.
• The same cell can't be used twice, e.g. "ABA" on a 1 × 2 grid.
• A single-letter word.

Complexity: O(R·C·3L) time (after the first step, each cell has at most 3 unvisited directions), O(L) recursion depth. Interview bonus: prune early if the board's letter counts can't cover the word.

Problem: The XOR total of a subset is the XOR of all its elements (0 for the empty subset). Return the sum of the XOR totals over every subset of nums.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 12 · 1 ≤ nums[i] ≤ 20

From brute force to the pattern: Enumerating all 2ⁿ subsets is fine for n ≤ 12. (A neat trick: the answer is (OR of all numbers) × 2ⁿ⁻¹.)

Spot it: "every subset" with a tiny n (≤ 12) is the take/skip decision tree.

Approach (step by step):

1. dfs(index, xor_so_far): xor_so_far is the XOR of the numbers chosen so far.
2. If index == len(nums), we've reached a leaf (one complete subset), so return xor_so_far.
3. Otherwise return dfs(index + 1, xor_so_far ^ nums[index]) (take) + dfs(index + 1, xor_so_far) (skip).
4. There's no explicit un-choose: xor_so_far is passed as a value, so each branch gets its own copy automatically.

from typing import List

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        self.nums = nums
        return self.dfs(0, 0)

    def dfs(self, index, xor_so_far):
        # 'xor_so_far' = XOR of the numbers taken so far on this branch
        if index == len(self.nums):
            return xor_so_far               # leaf: the XOR total of one complete subset
        # ^ is XOR: it combines two numbers bit by bit (1 where the bits differ)
        take_total = self.dfs(index + 1, xor_so_far ^ self.nums[index])
        skip_total = self.dfs(index + 1, xor_so_far)
        return take_total + skip_total      # add up the leaves of both branches

What the code is doing, line by line:

1. subsetXORSum stores nums and starts at index 0 with an XOR of 0 (the empty subset).
2. dfs(index, xor_so_far) decides about nums[index]. At a leaf (index == len(nums)) one whole subset is decided, so it returns that subset's XOR total.
3. take_total explores the branch that includes nums[index] (XOR it in with ^); skip_total explores the branch that leaves it out.
4. The function returns the sum of both branches, so the very first call returns the sum over all subsets.
5. There is no explicit un-choose: xor_so_far is a plain number passed by value, so each branch gets its own copy automatically.

Dry run on the example:

(nums = [1, 3]; rows are listed in the order the calls finish.)

Edge cases to test:

• A single element → that element.
• Duplicate values.
• Zeros in the array.

Complexity: O(2ⁿ) time, O(n) recursion depth. (Math shortcut: OR of all numbers × 2ⁿ⁻¹.)

Problem: Each digit 2–9 maps to letters as on a phone keypad. Given a digit string, return every letter string it could spell.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ digits.length ≤ 4 · digits[i] is a digit in the range ['2', '9'].

From brute force to the pattern: There are up to 4ⁿ combinations, so the output is that size. Backtracking (or iteratively extending a list of prefixes) builds each combination once.

Spot it: "return all possible combinations": one decision per digit, and the choices are that digit's letters.

Approach (step by step):

1. If digits is empty, return [] (an edge case LeetCode tests).
2. Map each digit to its letters.
3. backtrack(index): if index == len(digits), record ''.join(path).
4. For each letter of digits[index]: append it, recurse backtrack(index + 1), pop it.

from typing import List

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if len(digits) == 0:
            return []                       # no digits means no combinations (not [""])
        # the letters printed on each phone key
        self.phone = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
                      "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
        self.digits = digits
        self.path = []                      # letters chosen so far, one per digit
        self.results = []
        self.backtrack(0)
        return self.results

    def backtrack(self, index):
        # 'index' = which digit we are choosing a letter for
        if index == len(self.digits):
            # one letter per digit: join the list into a string (this also makes the copy)
            self.results.append("".join(self.path))
            return
        letters = self.phone[self.digits[index]]
        for letter in letters:              # choices = the letters of the current digit
            self.path.append(letter)        # choose
            self.backtrack(index + 1)       # explore the next digit
            self.path.pop()                 # un-choose

What the code is doing, line by line:

1. An empty input returns [] straight away; LeetCode expects that, not [""].
2. phone is a dictionary from each digit to its letters. path collects one letter per digit.
3. backtrack(index) picks a letter for digits[index]. When index reaches the end, "".join(path) glues the letters into a new string and saves it.
4. Otherwise it loops over that digit's letters: append, recurse to the next digit, pop.

Dry run on the example:

(digits = "23", 3 × 3 = 9 strings.)

Edge cases to test:

• An empty input → [] (not [""]).
• Digits 7 and 9 have four letters.
• A single digit.

Complexity: O(4ⁿ · n) time (up to 4 letters per digit), O(n) recursion depth.

Problem: Like Subsets (78), but nums may contain duplicates. Return all subsets without duplicate subsets.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10 · -10 ≤ nums[i] ≤ 10

From brute force to the pattern: Generating every subset and de-duplicating with a set of tuples works but wastes effort. Sorting plus the "skip equal siblings" rule never creates a duplicate in the first place.

Spot it: "all subsets" + "may contain duplicates" calls for the sort + skip-equal-siblings template.

Approach (step by step):

1. Sort so equal values sit next to each other.
2. backtrack(start): record a copy of path at every node. Each node is a valid subset.
3. Loop i from start. If i > start and nums[i] == nums[i−1], skip it: that value was already tried at this depth, and would produce the same subsets.
4. Choose nums[i], recurse with backtrack(i + 1), then pop.

from typing import List

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()                         # duplicates become neighbours
        self.nums = nums
        self.path = []
        self.results = []
        self.backtrack(0)
        return self.results

    def backtrack(self, start):
        self.results.append(self.path[:])   # every node of the tree is a subset
        for i in range(start, len(self.nums)):
            if i > start and self.nums[i] == self.nums[i - 1]:
                continue                    # same value at the same depth: duplicate branch
            self.path.append(self.nums[i])  # choose
            self.backtrack(i + 1)           # explore; i + 1: each element used at most once
            self.path.pop()                 # un-choose

What the code is doing, line by line:

1. Sort first so equal values sit side by side; then store everything on self and start at index 0.
2. backtrack(start) saves a copy of path immediately: every node is a valid subset.
3. The loop offers each later number as the next element. If i > start and the value equals the one just before it, that value was already offered at this depth, so the branch would repeat subsets: skip it.
4. i > start (not i > 0) matters: the first copy at each depth is still allowed, which is how [2, 2] gets built.
5. Choose, recurse with i + 1, pop.

Dry run on the example:

(nums = [1, 2, 2].)

Edge cases to test:

• All elements equal, e.g. [2, 2, 2].
• No duplicates → same as Subsets.
• The empty subset is always included.

Complexity: O(n · 2ⁿ) time, O(n) recursion depth.

Problem: Given candidates (may contain duplicates) and target, return every unique combination that sums to target. Each candidate may be used at most once.

Solve it on LeetCode ↗

Constraints: 1 ≤ candidates.length ≤ 100 · 1 ≤ candidates[i] ≤ 50 · 1 ≤ target ≤ 30

From brute force to the pattern: Enumerating subsets and filtering by sum with de-duplication is O(2ⁿ) with wasted duplicates. Sorted backtracking with sibling skipping and early stopping explores only distinct combinations.

Spot it: This is Combination Sum (39) with two changes: no reuse (recurse with i + 1) and duplicate inputs (skip equal siblings).

Approach (step by step):

1. Sort the candidates.
2. backtrack(start, remaining): if remaining == 0, record a copy.
3. Loop i from start. Skip it if i > start and it equals the previous value. break as soon as candidates[i] > remaining.
4. Choose it, recurse with backtrack(i + 1, remaining − number), then pop.

from typing import List

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()               # equal values side by side, and lets us break early
        self.candidates = candidates
        self.path = []
        self.results = []
        self.backtrack(0, target)
        return self.results

    def backtrack(self, start, remaining):
        if remaining == 0:
            self.results.append(self.path[:])   # exact hit: save a COPY
            return
        for i in range(start, len(self.candidates)):
            if i > start and self.candidates[i] == self.candidates[i - 1]:
                continue                # skip a duplicate sibling (same value, same depth)
            number = self.candidates[i]
            if number > remaining:
                break                   # sorted: nothing later fits either
            self.path.append(number)            # choose
            self.backtrack(i + 1, remaining - number)   # explore; i + 1: each candidate used once
            self.path.pop()                     # un-choose

What the code is doing, line by line:

1. Sort the candidates, store them, and start with the whole target remaining.
2. If remaining == 0, save a copy of path.
3. In the loop, first skip duplicate siblings (i > start and same value as the previous one), exactly like Subsets II.
4. Then stop the whole loop with break as soon as a number is bigger than what remains (the list is sorted).
5. Choose the number and recurse with i + 1, because each candidate may be used at most once. Pop to undo.

Dry run on the example:

(candidates = [10,1,2,7,6,1,5] sorted to [1,1,2,5,6,7,10], target = 8.)

Edge cases to test:

• Many repeated candidates, e.g. [1, 1, 1, 1].
• No combination exists.
• Candidates larger than the target.

Complexity: O(2ⁿ · n) time in the worst case, O(n) recursion depth.

Problem: Return every well-formed string made of n pairs of parentheses.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ n ≤ 8

From brute force to the pattern: Generating all 2²ⁿ strings and filtering the valid ones is wasteful. Respecting the two rules while building generates only valid strings (the Catalan number of them).

Spot it: "generate all" valid strings is backtracking where the validity rules prune as you go, so you never build an invalid string.

Approach (step by step):

1. Track how many '(' (open_count) and ')' (close_count) have been placed.
2. When the string has length 2n, record it.
3. You may add '(' while open_count < n.
4. You may add ')' only while close_count < open_count, meaning there's an unmatched '(' to close.
5. Each addition is choose → recurse → pop.

from typing import List

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        self.n = n
        self.path = []              # characters placed so far
        self.results = []
        self.backtrack(0, 0)
        return self.results

    def backtrack(self, open_count, close_count):
        # open_count / close_count = how many '(' and ')' are already in path
        if len(self.path) == 2 * self.n:
            self.results.append("".join(self.path))     # n pairs placed: save the string
            return
        if open_count < self.n:                 # still have '(' left to place
            self.path.append("(")
            self.backtrack(open_count + 1, close_count)
            self.path.pop()
        if close_count < open_count:            # a ')' must match an earlier unmatched '('
            self.path.append(")")
            self.backtrack(open_count, close_count + 1)
            self.path.pop()

What the code is doing, line by line:

1. generateParenthesis stores n, creates path and results, and starts with no brackets placed.
2. When path has 2 * n characters, all pairs are placed; it is joined into a string and saved.
3. Choice 1: add '(', allowed only while fewer than n have been used.
4. Choice 2: add ')', allowed only while there is an unmatched '(' (close_count < open_count). These two rules prune every invalid string before it is built.
5. Each choice is the usual append → recurse → pop.

Dry run on the example:

(n = 3: 5 strings.)

Edge cases to test:

• n = 1 → ["()"].
• Never letting close exceed open.
• Larger n: the count grows like the Catalan numbers (5 for n = 3).

Complexity: Catalan number of results, O(4ⁿ / √n) time overall; O(n) recursion depth.

Problem: Split a string into pieces so that every piece is a palindrome. Return every possible split.

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 16 · s contains only lowercase English letters.

From brute force to the pattern: Trying every cut pattern is 2ⁿ⁻¹ partitions and checking each is O(n). Backtracking only continues from palindromic pieces, and a palindrome table makes each check O(1).

Spot it: "return all possible partitions". The choice at each step is where to cut next. That's backtracking over cut positions.

Approach (step by step):

1. backtrack(start): the prefix before start is already cut into palindromes.
2. If start == len(s), record a copy of the pieces.
3. For each end from start to the last index, take the piece s[start:end+1].
4. If the piece is a palindrome (checked with a two-pointer helper, is_palindrome): append it, recurse with backtrack(end + 1), pop it. Otherwise prune.

from typing import List

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        self.s = s
        self.path = []              # palindromic pieces cut so far
        self.results = []
        self.backtrack(0)
        return self.results

    def backtrack(self, start):
        # everything before 'start' is already cut into palindromes
        if start == len(self.s):
            self.results.append(self.path[:])   # the whole string is cut up: save a COPY
            return
        for end in range(start, len(self.s)):   # choice = where this piece ends
            if self.is_palindrome(start, end):  # only palindromic pieces may be chosen
                piece = self.s[start:end + 1]
                self.path.append(piece)         # choose
                self.backtrack(end + 1)         # explore the rest of the string
                self.path.pop()                 # un-choose

    def is_palindrome(self, left, right):
        # two pointers walk inwards; any mismatch means "not a palindrome"
        while left < right:
            if self.s[left] != self.s[right]:
                return False
            left = left + 1
            right = right - 1
        return True

What the code is doing, line by line:

1. partition stores the string, sets up path (pieces so far) and results, and starts cutting at index 0.
2. backtrack(start): if start reached the end, every character belongs to a piece, so a copy of the pieces is saved.
3. Otherwise try every possible end of the next piece. is_palindrome(start, end) prunes pieces that are not palindromes.
4. For a good piece, slice it out with s[start:end + 1] (end is included), append it, recurse from end + 1, then pop.
5. is_palindrome uses two pointers moving towards each other; the first mismatched pair means "no", and if they meet without a mismatch the piece reads the same both ways.

Dry run on the example:

(s = "aab".)

Edge cases to test:

• A single character → [["a"]].
• All the same letter (many partitions).
• No palindrome longer than 1 → just single letters.

Complexity: O(n · 2ⁿ) time (2ⁿ⁻¹ ways to cut, O(n) palindrome checks), O(n) recursion depth. Precompute a palindrome table to speed up the checks.

Problem: Fill the empty cells ('.') of a 9×9 Sudoku so that every row, column and 3×3 box contains the digits 1–9 exactly once. Modify the board in place. A unique solution is guaranteed.

Solve it on LeetCode ↗

Constraints: board.length == 9 · board[i].length == 9 · board[i][j] is a digit or '.'. · It is guaranteed that the input board has only one solution.

From brute force to the pattern: Filling every empty cell with every digit and checking at the end is astronomically slow. Backtracking checks each placement immediately and abandons a branch as soon as a contradiction appears.

Spot it: This is constraint satisfaction: fill blanks one by one, prune clashing digits, and undo on dead ends. Because one solution is enough, the recursion returns True to stop everything as soon as it finds one.

Approach (step by step):

1. Build sets of used digits for each row, column and box, and list the empty cells.
2. backtrack(empty_index): if empty_index == len(empty_cells), every blank is filled, so return True.
3. For blank (row, col) in box (row // 3) * 3 + col // 3, try digits 1–9 that aren't in the row, column or box sets.
4. Place the digit and add it to the three sets. If backtrack(empty_index + 1) returns True, pass True straight up.
5. Otherwise remove the digit from the sets and the board (un-choose) and try the next one. If no digit fits, return False and the caller backtracks.

from typing import List

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        self.board = board
        # one set of digits already used per row, per column and per 3x3 box
        self.row_digits = []
        self.col_digits = []
        self.box_digits = []
        for i in range(9):
            self.row_digits.append(set())
            self.col_digits.append(set())
            self.box_digits.append(set())
        self.empty_cells = []           # every blank cell as [row, col]
        for row in range(9):
            for col in range(9):
                digit = board[row][col]
                if digit == ".":
                    self.empty_cells.append([row, col])
                else:
                    box = self.box_index(row, col)
                    self.row_digits[row].add(digit)
                    self.col_digits[col].add(digit)
                    self.box_digits[box].add(digit)
        self.backtrack(0)

    def box_index(self, row, col):
        # boxes are numbered 0..8, left to right, top to bottom
        return (row // 3) * 3 + col // 3

    def backtrack(self, empty_index):
        # 'empty_index' = which blank cell we fill next
        if empty_index == len(self.empty_cells):
            return True                 # all blanks filled: solved
        cell = self.empty_cells[empty_index]
        row = cell[0]
        col = cell[1]
        box = self.box_index(row, col)
        for digit in "123456789":
            if digit in self.row_digits[row] or digit in self.col_digits[col]:
                continue                # clash in the row or column: prune
            if digit in self.box_digits[box]:
                continue                # clash in the box: prune
            # choose: write the digit and record it in all three sets
            self.board[row][col] = digit
            self.row_digits[row].add(digit)
            self.col_digits[col].add(digit)
            self.box_digits[box].add(digit)
            if self.backtrack(empty_index + 1):
                return True             # stop at the first full solution
            # un-choose: this digit led to a dead end
            self.row_digits[row].remove(digit)
            self.col_digits[col].remove(digit)
            self.box_digits[box].remove(digit)
            self.board[row][col] = "."
        return False                    # no digit fits: the caller tries its next digit

What the code is doing, line by line:

1. solveSudoku builds 9 empty sets for rows, 9 for columns and 9 for boxes with a plain loop, then scans the board once: blanks go into empty_cells, given digits go into their row, column and box sets.
2. box_index turns a cell into its box number: row // 3 is the box-row (0, 1 or 2), col // 3 the box-column, and box-row * 3 + box-column gives 0..8.
3. backtrack(empty_index) fills one blank. If every blank is filled it returns True.
4. For the current blank it tries the digits 1–9, skipping any digit already in the cell's row, column or box (pruning).
5. A digit that fits is written to the board and added to the three sets. If the rest of the puzzle can then be solved, True is passed straight up and the search stops.
6. If not, the digit is removed from the sets and the cell becomes '.' again (un-choose). If no digit fits, False tells the previous blank to try its next digit.

Dry run on the example:

(The first few steps on the LeetCode example; the full search is too long to list. Note that the early guess 1 at (0,2) is later undone and replaced by 4.)

Edge cases to test:

• Puzzles that need deep backtracking.
• A nearly complete board.
• Restoring the sets correctly when undoing a choice.

Complexity: Exponential in the worst case (≤ 9^blanks), but the set-based pruning makes real puzzles fast. O(81) extra space.

Problem: Given a letter grid and a list of words, return every word that can be traced through 4-adjacent cells without reusing a cell inside a word.

Solve it on LeetCode ↗

Constraints: m == board.length · n == board[i].length · 1 ≤ m, n ≤ 12 · board[i][j] is a lowercase English letter. · 1 ≤ words.length ≤ 3 * 10⁴ · 1 ≤ words[i].length ≤ 10 · words[i] consists of lowercase English letters. · All the strings of words are unique.

From brute force to the pattern: One backtracking search per word is O(words · r · c · 4^L). A trie lets one DFS check every word at once and prune any path that isn't a prefix; removing found words keeps it from repeating work.

Spot it: This is Word Search (79) for many words at once. Running 79 once per word is too slow. Put all words in a Trie and backtrack over the grid once, pruning the moment the current path isn't a prefix of any word.

Approach (step by step):

1. Build a Trie (nested dicts). At the node where a word ends, store the word under the key '$'.
2. From every cell whose letter starts some word, DFS while walking the Trie in lockstep.
3. If the next cell's letter isn't a child of the current Trie node, don't go there (prune).
4. When a node has '$', record the word and pop it, so each word is reported once.
5. Mark the cell '#' while it's on the path and restore it afterwards (choose / un-choose).
6. Optimization: when a Trie node has no children left, delete it from its parent so later searches skip dead branches.

from typing import List

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        # build the trie: nested dicts, one level per letter
        self.root = {}
        for word in words:
            node = self.root
            for letter in word:
                if letter not in node:
                    node[letter] = {}       # new branch for this letter
                node = node[letter]
            node["$"] = word                # end-of-word marker stores the word itself
        self.board = board
        self.rows = len(board)
        self.cols = len(board[0])
        # the 4 neighbours as [row change, column change]: up, right, down, left
        self.directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]
        self.results = []
        for row in range(self.rows):
            for col in range(self.cols):
                if board[row][col] in self.root:    # only start where some word starts
                    self.dfs(row, col, self.root)
        return self.results

    def dfs(self, row, col, parent_node):
        letter = self.board[row][col]
        node = parent_node[letter]          # walk one step down the trie with this letter
        if "$" in node:
            self.results.append(node["$"])  # a whole word ends here
            del node["$"]                   # remove the marker so it is reported once
        self.board[row][col] = "#"          # choose: this cell is on the current path
        for direction in self.directions:
            next_row = row + direction[0]
            next_col = col + direction[1]
            if next_row < 0 or next_row >= self.rows or next_col < 0 or next_col >= self.cols:
                continue                    # off the board
            if self.board[next_row][next_col] in node:  # the trie prunes here
                self.dfs(next_row, next_col, node)
        self.board[row][col] = letter       # un-choose: put the letter back
        if len(node) == 0:
            del parent_node[letter]         # branch fully used up: remove it from the trie

What the code is doing, line by line:

1. First build a trie out of nested dictionaries: each key is a letter leading to the next level. Where a word ends, the key '$' stores the whole word.
2. Store the board and its size, list the four directions, and start a DFS from every cell whose letter begins some word (is a key of the root).
3. dfs(row, col, parent_node) steps from parent_node to the child for this cell's letter. If that child has '$', a word is complete: save it and delete the marker so it can't be saved twice.
4. Choose: mark the cell '#'. Explore: for each in-bounds neighbour, recurse only if its letter is a child of the current trie node. Any path that is not a prefix of some word is never walked.
5. Un-choose: restore the letter. Then, if the trie node has become empty (all its words found), delete it from its parent so later searches skip that dead branch.

Dry run on the example:

(Board oaan / etae / ihkr / iflv, words [oath, pea, eat, rain]; only the meaningful steps are listed.)

Edge cases to test:

• The same word reachable by several paths (report it once).
• Words that are prefixes of other words.
• No words found → [].

Complexity: O(R·C·4·3L−1) time in the worst case (L = longest word), but Trie pruning keeps it far lower in practice. O(total letters in words) space for the Trie.

Problem: Return all combinations of k numbers chosen from 1..n (order inside a combination doesn't matter).

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ n ≤ 20 · 1 ≤ k ≤ n

From brute force to the pattern: Generating all orderings and de-duplicating is wasteful. Increasing order produces each combination once; pruning when not enough numbers remain skips dead branches. O(k · C(n, k)).

Spot it: "All combinations" → backtracking. Choosing numbers in increasing order (each choice starts after the previous one) produces every combination exactly once, never [2, 1] as well as [1, 2].

Approach:

1. backtrack(start) extends the current path with numbers from start..n.
2. If path has k numbers, record a copy and return.
3. Otherwise for each x from start to n: choose x (append), explore backtrack(x + 1), un-choose (pop).

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result = []
        path = []

        def backtrack(start):
            if len(path) == k:
                result.append(path[:])     # a copy: path keeps changing
                return
            for x in range(start, n + 1):
                path.append(x)             # choose
                backtrack(x + 1)           # explore: only bigger numbers may follow
                path.pop()                 # un-choose

        backtrack(1)
        return result

What the code is doing, line by line:

1. path: the combination being built; result: the finished ones.
2. if len(path) == k: a full combination. path[:] stores a copy; storing path itself would leave every entry pointing at the same list, which ends up empty.
3. for x in range(start, n + 1): only numbers after the last one chosen, which is what prevents duplicates in a different order.
4. path.append(x), backtrack(x + 1), path.pop(): choose, explore, un-choose. The pattern's chant.
5. Optional pruning: if fewer than k − len(path) numbers remain in start..n, this branch can't finish. Stopping the loop at n − (k − len(path)) + 1 skips it.

Dry run on the example:

n = 4, k = 2 (LeetCode Example 1). Returns [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]].

Edge cases to test:

• k = n → one combination.
• k = 1 → n single numbers.
• n = 1.

Complexity: O(k · C(n, k)) time (each of the C(n, k) answers is copied in O(k)), O(k) recursion space besides the output.

Problem: Return all distinct permutations of nums, which may contain duplicates.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 8 · -10 ≤ nums[i] ≤ 10

From brute force to the pattern: Generating all n! orderings and putting them in a set does the duplicate work anyway; skipping duplicates prunes it.

Spot it: All arrangements → backtracking. Duplicates create identical branches; after sorting, equal values sit together, and allowing equal values only in left-to-right order removes every repeat.

Why not another pattern? Generating all n! permutations and deduplicating with a set wastes time on repeats.

Approach:

1. Sort nums; keep a used flag per index.
2. At each depth, try each unused index i, skipping it if nums[i] == nums[i − 1] and index i − 1 is not used.
3. When the path has n items, record a copy.

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums = sorted(nums)  # equal values become neighbours
        used = [False] * len(nums)
        result = []
        path = []

        def place():
            if len(path) == len(nums):
                result.append(path[:])
                return
            for i in range(len(nums)):
                if used[i]:
                    continue
                if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                    continue  # equal copies are used left to right only: no repeats
                used[i] = True
                path.append(nums[i])
                place()
                path.pop()  # undo the choice
                used[i] = False

        place()
        return result

What the code is doing, line by line:

1. Sorting puts copies of the same value next to each other.
2. Requiring copy i − 1 to be used before copy i fixes one order among identical values, so each distinct permutation is built once.
3. path[:] stores a snapshot, because path keeps changing.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All equal values → one permutation.
• No duplicates (same as Permutations).
• Single element.

Complexity: O(n · n!) time in the worst case (all distinct), O(n) recursion space.

Problem: Return every string obtainable by changing the case of each letter in s independently.

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 12 · s consists of lowercase English letters, uppercase English letters, and digits.

From brute force to the pattern: Checking all 2^n masks including digit positions creates duplicates; branching only on letters avoids them.

Spot it: Each letter is a binary choice → backtracking (or building level by level): 2^(letters) results.

Why not another pattern? Iterating over all 2^n bitmasks also works but must skip digits; the branch-per-letter form is simpler.

Approach:

1. Start with [""].
2. For each character: if it's a letter, extend every partial string with both cases; otherwise extend with the character.

class Solution:
    def letterCasePermutation(self, s: str) -> List[str]:
        results = [""]
        for ch in s:
            if ch.isalpha():
                results = [r + c for r in results for c in (ch.lower(), ch.upper())]  # branch into two cases
            else:
                results = [r + ch for r in results]  # digits don't branch
        return results

What the code is doing, line by line:

1. Each letter doubles the number of partial strings; digits just extend them.
2. This is the backtracking tree built breadth-first, level by level.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Only digits → one string.
• Mixed case input.
• A single letter → two strings.

Complexity: O(n · 2^L) time and space (L = number of letters).

Problem: Return, sorted, all numbers in [low, high] whose digits each increase by exactly 1 (like 1234).

Solve it on LeetCode ↗

Constraints: 10 ≤ low ≤ high ≤ 10^9

From brute force to the pattern: Scanning [low, high] is up to 10⁹ numbers; there are only 36 candidates.

Spot it: There are only 36 such numbers (lengths 2–9). Each is a window of "123456789", so enumerate by length then start — already sorted.

Why not another pattern? Checking every number in [low, high] is up to 10⁹ checks.

Approach:

1. For each length from len(str(low)) to len(str(high)):
2. For each start 0..9 − length: x = int("123456789"[start:start + length]).
3. Keep x if low ≤ x ≤ high.

class Solution:
    def sequentialDigits(self, low: int, high: int) -> List[int]:
        digits = "123456789"
        result = []
        for length in range(len(str(low)), len(str(high)) + 1):
            for start in range(10 - length):
                x = int(digits[start:start + length])  # a window of consecutive digits
                if low <= x <= high:
                    result.append(x)
        return result

What the code is doing, line by line:

1. A sequential-digit number is fully determined by its first digit and its length.
2. Shorter numbers are smaller, and for equal length a later start is larger, so the output is sorted.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No numbers in range → [].
• high = 10⁹ (the largest is 123456789).
• low and high of the same length.

Complexity: O(1): at most 36 candidates.

Problem: Happy strings use a, b, c with no two equal neighbours. Return the k-th happy string of length n, or "".

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 10 · 1 ≤ k ≤ 100

From brute force to the pattern: Backtracking through the first k happy strings is O(k · n); block counting is O(n).

Spot it: The backtracking tree is regular: 3 choices for the first letter, then 2 each. Each first letter covers 2^(n−1) strings, each later letter 2^(remaining). Skip whole branches by integer division instead of listing them.

Why not another pattern? Generating all 3 · 2^(n−1) strings with backtracking works for n ≤ 10, but counting branches is O(n).

Approach:

1. If k > 3 · 2^(n−1), return "". Use k −= 1.
2. First letter: "abc"[k // 2^(n−1)], k %= 2^(n−1).
3. Each next position: the two letters differing from the previous one, in order; pick options[k // 2^(left)].

class Solution:
    def getHappyString(self, n: int, k: int) -> str:
        block = 1 << (n - 1)  # strings under each choice of the first letter
        if k > 3 * block:
            return ""
        k = k - 1
        result = ["abc"[k // block]]
        k = k % block
        for left in range(n - 2, -1, -1):  # letters still to place after this one
            options = [c for c in "abc" if c != result[-1]]  # two choices, alphabetical
            size = 1 << left
            result.append(options[k // size])  # which half k falls into
            k = k % size
        return "".join(result)

What the code is doing, line by line:

1. There are 3 · 2^(n−1) happy strings of length n.
2. After the first letter, every position has exactly two options (anything but the previous letter).
3. Each option covers 2^(positions left) strings, so k // size picks it and k % size moves inside it.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k larger than the count → "".
• n = 1.
• k = the last string.

Complexity: O(n) time and space.

Problem: Return the k-th permutation (1-indexed, in lexicographic order) of 1..n.

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 9 · 1 ≤ k ≤ n!

From brute force to the pattern: Listing permutations in order until the k-th is up to n! steps; block counting is O(n²).

Spot it: Backtracking would list k permutations. Instead, count the branches: with n digits left, each choice of the first digit covers (n − 1)! permutations, so (k − 1) // (n − 1)! tells which digit comes next. This is backtracking that skips whole subtrees.

Why not another pattern? Generating permutations in order until the k-th is O(k · n) with k up to n!.

Approach:

1. digits = [1..n], k −= 1 (0-indexed).
2. For each position: block = (remaining − 1)!; idx = k // block; take digits.pop(idx); k %= block.

from math import factorial

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        digits = [str(d) for d in range(1, n + 1)]
        k = k - 1  # 0-indexed
        result = []
        while digits:
            block = factorial(len(digits) - 1)  # permutations per choice of the next digit
            idx = k // block  # which block k falls into
            result.append(digits.pop(idx))
            k = k % block  # position inside that block
        return "".join(result)

What the code is doing, line by line:

1. With m digits left, choosing the next digit splits the remaining permutations into m equal blocks of (m − 1)!.
2. k // block picks the block (the digit), k % block is the index inside it.
3. Popping keeps the unused digits sorted for the next step.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k = 1 → digits in order.
• k = n! → digits reversed.
• n = 1.

Complexity: O(n²) time (list pops), O(n) space.

Problem: Can the four cards be combined with + − × / and parentheses to make exactly 24 (real division)?

Solve it on LeetCode ↗

Constraints: cards.length == 4 · 1 ≤ cards[i] ≤ 9

From brute force to the pattern: Writing out every bracketed expression string and evaluating it works but is fiddly; pair merging is the same search, cleaner.

Spot it: Every expression combines two values at a time. Backtracking: choose an ordered pair, replace it by each possible result, and recurse on the shorter list; with one value left, check it's 24 (with a small tolerance for division).

Why not another pattern? Enumerating expression strings with parentheses is messy and error-prone; combining pairs covers every bracket structure.

Approach:

1. If one number is left, return whether it's within 1e-6 of 24.
2. For each pair i ≠ j: the rest stays; try a + b, a − b, a · b, and a / b (if b ≠ 0).
3. Recurse with the rest plus the result; return true as soon as any branch works.

class Solution:
    def judgePoint24(self, cards: List[int]) -> bool:
        def solve(nums):
            if len(nums) == 1:
                return abs(nums[0] - 24) < 1e-6  # floats: allow tiny error
            for i in range(len(nums)):
                for j in range(len(nums)):
                    if i == j:
                        continue
                    rest = [nums[t] for t in range(len(nums)) if t != i and t != j]
                    a, b = nums[i], nums[j]
                    results = [a + b, a - b, a * b]  # ordered pairs cover b - a and b / a too
                    if b != 0:
                        results.append(a / b)
                    for r in results:
                        if solve(rest + [r]):  # combine two numbers into one
                            return True
            return False

        return solve([float(c) for c in cards])

What the code is doing, line by line:

1. Any expression tree combines two sub-results at its root, so repeatedly merging two numbers explores every tree.
2. Trying ordered pairs handles the non-commutative − and / in both directions.
3. Division can produce fractions like 1/3, so the final comparison uses a tolerance.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Division by zero (skip).
• Fractions needed (e.g. 8 / (3 − 8/3)).
• No solution → false.

Complexity: Constant: at most 12 · 4 · 6 · 4 · 2 · 4 ≈ 9,000 leaves for four cards.

Problem: Return the minimum number of integer-sided squares that exactly tile an n × m rectangle (n, m ≤ 13).

Solve it on LeetCode ↗

Constraints: 1 ≤ n, m ≤ 13

From brute force to the pattern: Trying squares at every free cell in any order explodes; the canonical lowest-leftmost order plus pruning keeps it small.

Spot it: No greedy or simple DP is correct (11 × 13 needs 6, the DP gives 8). With tiny sizes, backtracking: track the filled height of every column (a skyline), always place a square at the lowest-leftmost gap, try large squares first, and prune when the count reaches the best found.

Why not another pattern? The usual split DP (cut the rectangle in two) misses tilings that aren't made of two rectangles, like the 11 × 13 case.

Approach:

1. heights[c] = filled height of column c (rectangle n tall, m wide).
2. Find the column with the lowest height (leftmost). If it's n, all is filled: update the best.
3. The square's max size is limited by the run of equal-height columns and the remaining height. Try sizes from largest to 1.
4. Raise those columns, recurse with count + 1, then lower them back.

class Solution:
    def tilingRectangle(self, n: int, m: int) -> int:
        heights = [0] * m  # filled height of each column
        self.best = n * m  # all 1x1 squares

        def fill(count):
            if count >= self.best:
                return  # can't beat the best tiling found so far
            low = min(heights)
            if low == n:
                self.best = count  # everything is covered
                return
            start = heights.index(low)  # leftmost lowest column
            end = start
            while end < m and heights[end] == low and end - start + 1 <= n - low:
                end += 1  # widest square that fits here
            for size in range(end - start, 0, -1):  # big squares first
                for c in range(start, start + size):
                    heights[c] += size
                fill(count + 1)
                for c in range(start, start + size):
                    heights[c] -= size  # undo

        fill(0)
        return self.best

What the code is doing, line by line:

1. Filling the lowest, leftmost gap first means every tiling is built in one canonical order.
2. A square placed there can't be wider than the flat run of equal heights, nor taller than the space left.
3. Large squares first find good tilings early, which makes the count >= best pruning very effective.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• n == m → 1.
• n = 1 → m squares.
• 11 × 13 (needs 6, the split DP says 8).

Complexity: Exponential in the worst case, but fast for n, m ≤ 13 thanks to the pruning.

Problem: Assign each job to one of k workers to minimise the largest total working time (≤ 12 jobs).

Solve it on LeetCode ↗

Constraints: 1 ≤ k ≤ jobs.length ≤ 12 · 1 ≤ jobs[i] ≤ 10⁷

From brute force to the pattern: All kⁿ assignments is up to 12¹² without pruning. Symmetry breaking and bounding cut it to a small search.

Spot it: With 12 jobs, backtracking over assignments with strong pruning: sort jobs descending, stop any branch whose load reaches the best answer, and try only one of several workers with identical loads (they're interchangeable).

Why not another pattern? Greedy (give each job to the least loaded worker) isn't optimal; kⁿ assignments without pruning is too many.

Approach:

1. Sort jobs descending; loads = [0] * k; best = sum(jobs).
2. Place job i on each worker whose load + job < best, skipping loads already tried at this level.
3. When all jobs are placed, best = max(loads).

class Solution:
    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:
        jobs = sorted(jobs, reverse=True)  # big jobs first: bad branches fail early
        loads = [0] * k
        self.best = sum(jobs)

        def assign(i):
            if i == len(jobs):
                self.best = min(self.best, max(loads))
                return
            tried = set()
            for w in range(k):
                if loads[w] in tried or loads[w] + jobs[i] >= self.best:
                    continue  # same load = same outcome; or can't beat best
                tried.add(loads[w])
                loads[w] += jobs[i]
                assign(i + 1)
                loads[w] -= jobs[i]  # undo

        assign(0)
        return self.best

What the code is doing, line by line:

1. Workers with equal loads lead to symmetric subtrees, so only one of them is tried.
2. A branch whose new load would reach best can't improve it.
3. Placing big jobs first raises loads quickly, so pruning starts early.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k equals the number of jobs → the largest job.
• k = 1 → the sum.
• Many equal jobs (symmetry).

Complexity: Worst case O(kⁿ), much less in practice with the pruning (n ≤ 12).

Problem: Return the smallest number ≥ num with no zero digits whose digit product is divisible by t, or "-1". num can have 2·10⁵ digits.

Solve it on LeetCode ↗

Constraints: 2 ≤ num.length ≤ 2 * 10⁵ · num consists only of digits in the range ['0', '9']. · num does not contain leading zeros. · 1 ≤ t ≤ 10¹⁴

From brute force to the pattern: Testing num, num + 1, … is hopeless for 2·10⁵ digits. Scanning positions from the right with a greedy suffix is near-linear.

Spot it: Digits only supply the primes 2, 3, 5, 7, so if t has another prime factor the answer is -1. Otherwise, like "next greater number" problems, keep the longest possible prefix of num and raise one digit; the free suffix must cover what's left of t with the fewest digits (greedily divide by 9, 8, …, 2), placed after 1s in increasing order.

Why not another pattern? Incrementing the number and testing is hopeless with 2·10⁵ digits; a digit DP over the 4 prime exponents is possible but heavier.

Key insight: The fewest digits whose product is a multiple of r come from dividing r greedily by 9, 8, …, 2 (as in Minimum Factorization). Sorted ascending after leading 1s, they give the smallest suffix of a given length.

Approach:

1. If t has a prime factor other than 2, 3, 5, 7, return "-1".
2. If num has a 0, replace it and everything after with 1s (the smallest zero-free number above).
3. need[i] = what's left of t after the first i digits. If need[n] == 1, return num.
4. From the last position back: try digits num[i] + 1 … 9; if the remaining t fits in the n − i − 1 free digits, build the answer.
5. If no position works, use a longer number: 1…1 + the minimal digits, length max(n + 1, digits needed).

from math import gcd

class Solution:
    def smallestNumber(self, num: str, t: int) -> str:
        rest = t
        for p in (2, 3, 5, 7):
            while rest % p == 0:
                rest //= p
        if rest != 1:
            return "-1"  # t has a prime factor no digit can supply

        def min_digits(r):  # fewest digits whose product is a multiple of r, ascending
            out = []
            for d in range(9, 1, -1):
                while r % d == 0:
                    out.append(str(d))
                    r //= d
            return out[::-1]

        digits = list(num)
        if "0" in digits:
            z = digits.index("0")
            digits[z:] = ["1"] * (len(digits) - z)  # smallest zero-free number above num
        n = len(digits)
        need = [t]  # need[i]: part of t not yet covered by digits[:i]
        for ch in digits:
            need.append(need[-1] // gcd(need[-1], int(ch)))
        if need[n] == 1:
            return "".join(digits)
        for i in range(n - 1, -1, -1):  # rightmost position to raise = smallest result
            for d in range(int(digits[i]) + 1, 10):
                r = need[i] // gcd(need[i], d)
                tail = min_digits(r)
                free = n - i - 1
                if len(tail) <= free:
                    return "".join(digits[:i]) + str(d) + "1" * (free - len(tail)) + "".join(tail)
        tail = min_digits(t)
        length = max(n + 1, len(tail))  # no same-length answer: go one digit longer
        return "1" * (length - len(tail)) + "".join(tail)

What the code is doing, line by line:

1. Any prime other than 2, 3, 5, 7 can never divide a product of digits 1–9.
2. A zero must be raised; turning it into 1 (and everything after into 1s) is the smallest zero-free number ≥ num.
3. need[i] shrinks as each prefix digit contributes its factors (gcd removes what's covered).
4. Raising the rightmost possible digit keeps the longest prefix, giving the smallest result; the first d that works there is the smallest digit.
5. The free suffix is 1s then the minimal digits ascending; if nothing fits, the answer has more digits than num.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• num already works → num.
• num contains zeros.
• t with a prime factor like 13 → "-1".
• The answer is longer than num.

Complexity: O(n · log t) time: the backwards scan stops within about 50 positions once the free suffix is long enough.

Problem: Choose a subsequence of arr whose concatenation has all distinct letters. Return the maximum length.

Solve it on LeetCode ↗

Constraints: 1 ≤ arr.length ≤ 16 · 1 ≤ arr[i].length ≤ 26 · arr[i] contains only lowercase English letters.

From brute force to the pattern: Building and checking the concatenated strings for each subset is slower; masks make checks O(1).

Spot it: Choose-or-skip each string → backtracking, at most 2¹⁶ branches. Represent a string's letters as a bitmask so a clash is mask & other != 0.

Why not another pattern? A DP over letter sets is possible but the plain search is small enough and clearer.

Approach:

1. Turn each string into a mask; drop strings with repeated letters.
2. dfs(i, mask): either skip arr[i] or take it if mask & m == 0.
3. Track the best popcount(mask).

class Solution:
    def maxLength(self, arr: List[str]) -> int:
        masks = []
        for word in arr:
            m = 0
            for ch in word:
                bit = 1 << (ord(ch) - 97)
                if m & bit:
                    m = -1  # a repeated letter: this word can never be used
                    break
                m |= bit
            if m >= 0:
                masks.append(m)
        self.best = 0

        def dfs(i, used):
            self.best = max(self.best, bin(used).count("1"))
            for j in range(i, len(masks)):
                if used & masks[j] == 0:  # no shared letters
                    dfs(j + 1, used | masks[j])  # take word j (later words only)

        dfs(0, 0)
        return self.best

What the code is doing, line by line:

1. A 26-bit integer records which letters are used; AND tests for overlap in O(1).
2. Iterating j from i builds each subset once (combinations, not permutations).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Strings with internal duplicates (skip).
• All 26 letters used.
• Single string.

Complexity: O(2ⁿ) time in the worst case (n ≤ 16), O(n) recursion depth.

Problem: Remove the minimum number of parentheses to make the string valid; return all distinct results.

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 25 · s consists of lowercase English letters and parentheses '(' and ')'. · There will be at most 20 parentheses in s.

From brute force to the pattern: Trying every subset of removals is O(2ⁿ · n); counting first and pruning duplicates cuts most of it.

Spot it: First compute exactly how many ( and ) must go (a counter scan). Then backtracking removes that many, keeping only valid results; skipping a character equal to the previous one at the same level avoids duplicate work.

Why not another pattern? BFS removing one character per level also works but generates many duplicates; the counted backtracking prunes harder.

Approach:

1. Scan: ( → left += 1; ) → left −= 1 if left, else right += 1. These are the removals needed.
2. dfs(start, left, right, s): if both are 0 and s is valid, record it.
3. Try removing each bracket at i ≥ start (skip if s[i] == s[i − 1] for i > start).

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        left = right = 0  # how many "(" and ")" must be removed
        for ch in s:
            if ch == "(":
                left += 1
            elif ch == ")":
                if left:
                    left -= 1
                else:
                    right += 1

        def valid(t):
            bal = 0
            for ch in t:
                bal += (ch == "(") - (ch == ")")
                if bal < 0:
                    return False
            return bal == 0

        found = set()

        def dfs(start, left, right, t):
            if left == 0 and right == 0:
                if valid(t):
                    found.add(t)
                return
            for i in range(start, len(t)):
                if i > start and t[i] == t[i - 1]:
                    continue  # removing either of two equal neighbours gives the same string
                if t[i] == ")" and right:
                    dfs(i, left, right - 1, t[:i] + t[i + 1:])
                elif t[i] == "(" and left:
                    dfs(i, left - 1, right, t[:i] + t[i + 1:])

        dfs(0, left, right, s)
        return list(found)

What the code is doing, line by line:

1. The first scan gives the minimum: unmatched ) while scanning, and ( left open at the end.
2. Removing exactly that many keeps every answer minimal; the validity check filters wrong choices.
3. Restarting the loop at i (not i + 1) is correct because the string just got shorter at position i.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Already valid → [s].
• Only )( → [""].
• Letters mixed in.

Complexity: O(2ⁿ · n) in the worst case, much less with the counts and duplicate skipping.

Problem: Control a robot with move(), turnLeft(), turnRight() and clean() in an unknown room (no map, no position). Clean every reachable cell.

Solve it on LeetCode ↗ (Premium)

Constraints: m == room.length · n == room[i].length · 1 ≤ m ≤ 100 · 1 ≤ n ≤ 200 · room[i][j] is either 0 or 1 · 0 ≤ row < m · 0 ≤ col < n · room[row][col] == 1 · All the empty cells can be visited from the starting position

From brute force to the pattern: Random walking may never finish; DFS with physical backtracking visits each cell once.

Spot it: Exploring everything is DFS, but the robot can't jump back: undoing a step means physically going back — backtracking. Track visited cells in your own coordinates, starting from (0, 0) facing up.

Why not another pattern? BFS needs to teleport between frontier cells; the robot can only walk, so DFS with explicit backtracking fits.

Approach:

1. dfs(cell, dir): clean; for 4 directions (turning right each time): next cell = cell + dir.
2. If unvisited and robot.move() succeeds: dfs(next, dir), then go back (turn twice, move, turn twice).
3. Turn right to try the next direction.

class Solution:
    def cleanRoom(self, robot) -> None:
        dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]  # up, right, down, left (clockwise)
        visited = set()

        def go_back():
            robot.turnRight()
            robot.turnRight()
            robot.move()  # step back to the previous cell
            robot.turnRight()
            robot.turnRight()  # face the same way as before

        def dfs(r, c, d):
            visited.add((r, c))
            robot.clean()
            for k in range(4):
                nd = (d + k) % 4
                nr, nc = r + dirs[nd][0], c + dirs[nd][1]
                if (nr, nc) not in visited and robot.move():
                    dfs(nr, nc, nd)
                    go_back()  # undo the move (backtrack)
                robot.turnRight()  # try the next direction clockwise

        dfs(0, 0, 0)

What the code is doing, line by line:

1. Our coordinates are relative to the start; the robot's real position never matters.
2. Four right turns bring the robot back to its original direction, so after the loop it faces the way it came in.
3. go_back returns to the parent cell facing the same direction, exactly undoing the move.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A single open cell.
• Long corridors.
• Obstacles forming loops.

Complexity: O(N) moves for N open cells (each edge walked twice), O(N) space.

Problem: Count 4-directional walks from the start (1) to the end (2) that visit every non-obstacle cell exactly once.

Solve it on LeetCode ↗

Constraints: m == grid.length · n == grid[i].length · 1 ≤ m, n ≤ 20 · 1 ≤ m * n ≤ 20 · -1 ≤ grid[i][j] ≤ 2 · There is exactly one starting cell and one ending cell.

From brute force to the pattern: This is the exhaustive search; the cell count lets it reject incomplete paths at the end.

Spot it: Paths visiting each cell once on a tiny grid (≤ 20 cells) → backtracking: mark a cell, recurse, unmark.

Why not another pattern? DP over (cell, visited set) works with bitmasks but is overkill for 20 cells; plain backtracking is fast enough.

Approach:

1. Count the cells to walk (0s plus start); find the start.
2. dfs(r, c, left): at the end, count 1 if left == 0.
3. Mark the cell as visited (−1), recurse into neighbours, unmark.

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        to_visit = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    sr, sc = r, c
                if grid[r][c] != -1:
                    to_visit += 1  # every walkable cell, including start and end

        def dfs(r, c, left):
            if grid[r][c] == 2:
                return 1 if left == 1 else 0  # the end must be the last unvisited cell
            saved, grid[r][c] = grid[r][c], -1  # mark as visited
            paths = 0
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != -1:
                    paths += dfs(nr, nc, left - 1)
            grid[r][c] = saved  # unmark (backtrack)
            return paths

        return dfs(sr, sc, to_visit)

What the code is doing, line by line:

1. left counts cells not yet stepped on, including the current one.
2. Reaching the end with left == 1 means it's the final cell, so every cell was used.
3. Temporarily writing −1 doubles as the visited marker.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No valid path → 0.
• Start next to end with other cells left.
• Obstacles splitting the grid.

Complexity: O(3^k) time for k walkable cells (each step has at most 3 new directions), O(k) recursion.

Problem: Insert three dots into a digit string to form every valid IPv4 address (parts 0–255, no leading zeros).

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 20 · s consists of digits only.

From brute force to the pattern: Validating all C(n − 1, 3) dot placements is fine for n ≤ 20 but can't prune; backtracking stops invalid prefixes early.

Spot it: Choose where each of the 4 parts ends: a small decision tree (at most 3 choices per part) → backtracking. Prune a branch as soon as a part is invalid or the remaining digits can't fill the remaining parts.

Why not another pattern? Trying all C(n − 1, 3) dot placements and validating each works too, but backtracking stops bad prefixes early.

Approach:

1. place(start, parts): if 4 parts are chosen, record them when start == len(s).
2. Prune if the remaining digits are fewer than the parts left, or more than 3 per part.
3. Try part lengths 1–3: skip leading zeros (len > 1 and starts with 0) and values > 255.

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        result = []
        parts = []

        def place(start):
            left = 4 - len(parts)  # parts still to choose
            if left == 0:
                if start == len(s):
                    result.append(".".join(parts))  # used every digit
                return
            remaining = len(s) - start
            if remaining < left or remaining > 3 * left:
                return  # can't split the rest into `left` parts of 1-3 digits
            for length in range(1, 4):
                piece = s[start:start + length]
                if len(piece) < length:
                    break
                if (length > 1 and piece[0] == "0") or int(piece) > 255:
                    continue  # leading zero or out of range
                parts.append(piece)  # choose
                place(start + length)
                parts.pop()  # un-choose

        place(0)
        return result

What the code is doing, line by line:

1. Each level of the recursion picks the next part; there are exactly 4 levels.
2. The length check prunes hopeless branches early (for example a 20-digit string fails immediately).
3. "0" is a valid part, but "01" is not.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• "0000" → 0.0.0.0.
• Strings longer than 12 → [].
• Zeros inside numbers (101023).

Complexity: O(3⁴) branches at most, each costing O(n) to join: effectively constant.

Problem: Return an n-bit Gray code sequence: all 2ⁿ values starting at 0, consecutive values (and last-to-first) differ in exactly one bit.

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 16

From brute force to the pattern: Searching sequences with backtracking is exponential; reflection builds it directly.

Spot it: The recursive construction is a classic backtracking/reflection idea: the code for n bits is the code for n − 1 bits, followed by the same list reversed with the top bit set. Its closed form is i ^ (i >> 1).

Why not another pattern? Backtracking over sequences works for small n but is exponential to search.

Approach:

1. result = [0].
2. For each bit b: append x | (1 << b) for x in reversed(result).

class Solution:
    def grayCode(self, n: int) -> List[int]:
        result = [0]
        for b in range(n):
            result += [x | (1 << b) for x in reversed(result)]  # mirror and set the new bit
        return result

What the code is doing, line by line:

1. Inside each half, neighbours differ by one bit (induction); at the seam, the mirrored copies differ only in the new bit.
2. The last element is 1 << (n − 1), one bit from 0.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• n = 1 → [0, 1].
• Many valid sequences exist.
• Wrap-around condition.

Complexity: O(2ⁿ) time and space.

Problem: Can nums be split into k non-empty subsets with equal sums?

Solve it on LeetCode ↗

Constraints: 1 ≤ k ≤ nums.length ≤ 16 · 1 ≤ nums[i] ≤ 10⁴ · The frequency of each element is in the range [1, 4].

From brute force to the pattern: Unpruned assignment is kⁿ; a bitmask DP over subsets is O(n · 2ⁿ) and also works.

Spot it: Assign each number to a bucket → backtracking, with pruning: sort descending, cap each bucket at target, and treat buckets with equal loads as the same.

Why not another pattern? Trying all kⁿ assignments without pruning is too slow.

Approach:

1. If sum % k, false; target = sum / k; if the largest > target, false.
2. Place numbers largest first; try each bucket with room, skipping duplicate loads.
3. All placed → true.

class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        total = sum(nums)
        if total % k:
            return False
        target = total // k
        nums = sorted(nums, reverse=True)  # big numbers first: fail fast
        if nums[0] > target:
            return False
        buckets = [0] * k

        def place(i):
            if i == len(nums):
                return True  # every bucket must be exactly target
            tried = set()
            for b in range(k):
                if buckets[b] + nums[i] <= target and buckets[b] not in tried:
                    tried.add(buckets[b])  # equal loads are interchangeable
                    buckets[b] += nums[i]
                    if place(i + 1):
                        return True
                    buckets[b] -= nums[i]  # undo
            return False

        return place(0)

What the code is doing, line by line:

1. All numbers placed with no bucket over target means every bucket is exactly target.
2. Skipping equal loads removes symmetric branches (including all the empty buckets).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Sum not divisible by k.
• A number bigger than target.
• k = 1 → true.

Complexity: O(kⁿ) worst case, far less with the pruning (n ≤ 16).

Problem: Given n distinct binary strings of length n, return any length-n binary string not among them.

Solve it on LeetCode ↗

Constraints: n == nums.length · 1 ≤ n ≤ 16 · nums[i].length == n · nums[i] is either '0' or '1'. · All the strings of nums are unique.

From brute force to the pattern: Trying candidates against a set is O(n²) or so; the diagonal is O(n).

Spot it: Backtracking over strings would work, but Cantor's diagonal argument builds one directly: take the opposite of the i-th bit of the i-th string, so the result differs from every string somewhere.

Why not another pattern? Generating candidates and checking membership is fine for n ≤ 16 but the diagonal is O(n).

Approach:

1. For each i: output '1' if nums[i][i] == '0' else '0'.

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        return "".join("1" if nums[i][i] == "0" else "0" for i in range(len(nums)))  # differ from string i at bit i

What the code is doing, line by line:

1. The result differs from nums[i] at position i, so it equals none of them.
2. Any valid answer is accepted.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• n = 1.
• All strings share prefixes.
• Several valid answers.

Complexity: O(n) time, O(n) space.

Problem: Return every way to split s into dictionary words, as space-separated sentences (any order).

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 20 · 1 ≤ wordDict.length ≤ 1000 · 1 ≤ wordDict[i].length ≤ 10 · s and wordDict[i] consist of only lowercase English letters. · All the strings of wordDict are unique. · Input is generated in a way that the length of the answer doesn't exceed 10⁵.

From brute force to the pattern: Plain backtracking repeats suffixes; memoisation reuses them.

Spot it: All sentences → backtracking over word prefixes; the same suffix is reached many ways, so memoise the sentences for each start index.

Why not another pattern? Word Break's boolean DP only says whether a split exists, not what they are.

Approach:

1. build(i): all sentences for s[i:]; build(len(s)) = [""].
2. For each word s[i:j] in the dictionary: prefix it to each sentence of build(j).

from functools import lru_cache

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        words = set(wordDict)

        @lru_cache(maxsize=None)
        def build(i):  # every sentence for s[i:]
            if i == len(s):
                return [""]
            out = []
            for j in range(i + 1, len(s) + 1):
                word = s[i:j]
                if word in words:
                    for rest in build(j):
                        out.append(word + (" " + rest if rest else ""))  # word, then the rest
            return out

        return build(0)

What the code is doing, line by line:

1. [""] at the end lets the last word be added without a trailing space.
2. Memoisation shares suffix results between different prefixes.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No split → [].
• Words reused.
• Overlapping words (cat / cats).

Complexity: Proportional to the output size (can be exponential), O(n²) work per index otherwise.

Problem: Find all combinations of k distinct digits 1–9 that sum to n.

Solve it on LeetCode ↗

Constraints: 2 ≤ k ≤ 9 · 1 ≤ n ≤ 60

From brute force to the pattern: All 512 subsets would also work; backtracking is the standard approach.

Spot it: Choose a set of numbers → backtracking with increasing digits (no duplicates), pruning when the sum exceeds n.

Why not another pattern? Trying all subsets of 9 digits (512) works too; backtracking prunes earlier.

Approach:

1. pick(start, remaining): if k digits chosen, record when remaining == 0.
2. Try digits start..9 while d ≤ remaining.

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        result = []
        path = []

        def pick(start, remaining):
            if len(path) == k:
                if remaining == 0:
                    result.append(path[:])
                return
            for d in range(start, 10):
                if d > remaining:
                    break  # larger digits only overshoot more
                path.append(d)
                pick(d + 1, remaining - d)  # next digit must be larger
                path.pop()

        pick(1, n)
        return result

What the code is doing, line by line:

1. Increasing digits make each combination appear once.
2. Digits are tried in increasing order, so the first one too big ends the loop.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No solution → [].
• k = 9.
• n too small.

Complexity: At most C(9, k) combinations; tiny.

Problem: Count permutations of 1..n where for every position i, perm[i] divides i or i divides perm[i].

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 15

From brute force to the pattern: All permutations: n!; pruned backtracking (or bitmask DP O(n · 2ⁿ)).

Spot it: Place numbers position by position with pruning → backtracking (or a bitmask DP over used numbers).

Why not another pattern? Checking all n! permutations is too slow for n = 15.

Approach:

1. place(pos): if pos > n, count one.
2. Try every unused x with x % pos == 0 or pos % x == 0.

class Solution:
    def countArrangement(self, n: int) -> int:
        used = [False] * (n + 1)

        def place(pos):
            if pos > n:
                return 1  # every position is filled
            total = 0
            for x in range(1, n + 1):
                if not used[x] and (x % pos == 0 or pos % x == 0):
                    used[x] = True
                    total += place(pos + 1)
                    used[x] = False
            return total

        return place(1)

What the code is doing, line by line:

1. The divisibility rule prunes most branches early.
2. Filling from position 1 upward checks each placement once.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• n = 1 → 1.
• n = 2 → 2.
• Larger n (pruning matters).

Complexity: Far below n! thanks to pruning; fine for n ≤ 15.