Backtracking

Find every combination summing to a target, with unlimited reuse of each candidate.

Trigger

'Combinations that sum to X' with reuse allowed.

Approach

1. Reuse means the recursion passes the **same** index, not index+1.
2. Passing a start index rather than iterating from zero is what prevents permutations of the same set.
3. Prune: sort the candidates and stop the loop once the remaining target goes negative.

Target complexity

O(n^(target/min)) in the worst case; the pruning is what makes it practical.

Pitfall

Iterating from zero instead of from the start index. You then generate the same combination in every order.

Say it out loud

“Reuse means I recurse with the same index rather than advancing. The start index is what prevents me from generating permutations of the same combination. And sorting lets me break out of the loop as soon as the remaining target goes negative, which is the pruning that matters.”

Solve on LeetCode

Generate every letter combination a digit string could represent on a phone keypad.

Trigger

'All combinations' from a fixed mapping — a cartesian product.

Approach

1. It is the cartesian product of the letter sets, so the count is the product of the sizes.
2. Backtracking over the digit positions, appending one letter at each level.
3. Guard the empty input — it should return an empty list, not a list containing an empty string.
4. `itertools.product` is a legitimate one-liner; be ready to write it out by hand too.

Target complexity

O(4ⁿ · n) worst case, O(n) stack.

Pitfall

Returning [""] for empty input. It is the test case that catches most submissions.

Say it out loud

“This is a cartesian product, so I'll do it with backtracking over digit positions. The edge case worth stating up front is the empty input — it should give an empty list, not a list containing the empty string.”

Solve on LeetCode

Return every way to split a string so that each piece is a palindrome.

Trigger

'All partitions' plus a validity condition on each piece.

Approach

1. Backtracking over cut positions: for each prefix that is a palindrome, recurse on the rest.
2. The palindrome check is the pruning — an invalid prefix cuts the whole branch.
3. Optimisation: precompute an is_palindrome table with DP, making each check O(1).

Target complexity

O(n · 2ⁿ) time, O(n) stack plus the output.

Pitfall

Re-checking the same substring for palindromicity across branches. Precompute the table.

Say it out loud

“It's backtracking over cut points, and the palindrome check doubles as the pruning. If I want to be careful about the constant, I'd precompute a DP table of which substrings are palindromes, so each check inside the recursion is constant.”

Solve on LeetCode

Generate every permutation of a list of distinct integers.

Trigger

'All orderings', 'permutations'.

Approach

1. n! outputs, so factorial is the floor.
2. Track which elements are used — a boolean array or a set.
3. Alternative: swap-based generation, which needs no extra structure but is harder to reason about with duplicates.

Target complexity

O(n! · n) time, O(n) space beyond the output.

Pitfall

Not resetting the used marker after the recursive call, which silently drops branches.

Say it out loud

“The output is factorial, so that's the bound. I'll track used elements with a boolean array and make sure I reset the flag on the way back out of the recursion — forgetting that is the classic bug and it fails silently by producing too few results.”

Solve on LeetCode

Generate every subset of a set of distinct integers.

Trigger

'All subsets', 'the power set'.

Approach

1. 2ⁿ subsets, so exponential output is the floor — say that so the complexity is not held against you.
2. Backtracking: at each index, either include the element or skip it.
3. Append a **copy** of the path, and pop after recursing.
4. Mention the bitmask alternative: iterate 0 to 2ⁿ−1 and read the bits.

Target complexity

O(2ⁿ · n) time (the n is the copying), O(n) stack.

Pitfall

Appending the path itself rather than a copy. Every entry then aliases the same empty list.

Say it out loud

“The output alone is exponential, so that's the lower bound. It's the base backtracking template — choose, explore, un-choose — and the thing I'll be careful with is appending a copy of the path, since I'm about to mutate it.”

Solve on LeetCode

Decide whether a word can be traced through adjacent cells of a grid.

Trigger

A grid plus a word — backtracking with a visited marker.

Approach

1. DFS from every cell whose letter matches the first character.
2. Mark the cell visited before recursing and **unmark it after** — that is the backtracking.
3. Marking in place (overwrite with a sentinel, restore afterwards) avoids a separate visited set.
4. Prune early: mismatch on the current character means return immediately.

Target complexity

O(m · n · 4^L) worst case, O(L) stack.

Pitfall

Not unmarking on the way out. The same cell then blocks other valid paths.

Say it out loud

“DFS from each matching starting cell, marking the current cell as I descend and unmarking it as I come back — that's what makes it backtracking rather than a plain flood fill. I can mark in place with a sentinel character and restore it, which avoids allocating a visited set.”

Solve on LeetCode

Place n queens on an n×n board so that none attack another, and return all solutions.

Trigger

The canonical pruning problem.

Approach

1. One queen per row, so the search is over column choices per row.
2. Three sets for the constraints: columns, and the two diagonals via (row − col) and (row + col).
3. Those sets make the conflict check O(1) — that is the whole optimisation.
4. Prune before descending, never after placing and checking.

Target complexity

O(n!) in the worst case, but the pruning cuts it enormously; O(n) space for the sets.

Pitfall

Scanning the board to check conflicts, which is O(n) per placement instead of O(1).

Say it out loud

“One queen per row reduces this to choosing a column per row. The trick is encoding the diagonals as row minus column and row plus column, so all three conflict checks are set lookups. That makes the pruning cheap enough to do before every descent, which is where all the savings come from.”

Solve on LeetCode

Find every word from a dictionary that can be traced through a grid of letters.

Trigger

A grid plus a word list — the give-away for a trie driving the backtracking.

Approach

1. Naive: run word search once per word — O(W · m · n · 4^L). Say it, then improve.
2. Build a trie of the dictionary, then DFS the grid once, walking the trie in parallel.
3. Prune hard: stop the moment the current prefix leaves the trie.
4. Remove found words from the trie so you do not re-report or re-explore them.

Target complexity

O(m·n·4^L) in the worst case, but the trie pruning is what makes it tractable.

Pitfall

Forgetting to un-mark visited cells on the way back out of the DFS.

Say it out loud

“Running word search per word repeats the same prefix work over and over. I'll build a trie of the dictionary and walk the grid once, descending the trie alongside the DFS. The moment a prefix isn't in the trie I stop — that pruning is the whole point of the structure here.”

Solve on LeetCode