THE RECURSION TREE
YOUR CALL
The hard backtracking problems look nothing alike — cut a string into palindromes, trace a word across a grid, place queens, fill a Sudoku — but every one is the same skeleton from deck 1: make a choice, recurse, undo it. What changes is only the shape of the choice (a cut point, a compass direction, a column, a digit) and the constraint that prunes the bad branches early. Two play out on a partition tree, three on a grid — each animated one decision at a time, with the dead branches struck out as they are pruned.
This is not a list of problems. It is 5 learning units, and every one runs the same four beats. Go in order and the problems stop feeling random.
5 PROBLEMS · EVERY ONE LINKS TO LEETCODE TO SOLVE
Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here. The number is the sheet's row, not your position — the deck teaches in the order that builds, so you will meet them slightly out of numerical sequence.
Five hard problems, one skeleton. The cards are the phrases in a statement that tell you the shape of the choice — a cut, a direction, a column, a digit — and whether memoisation is available.
recurse over the start index; keep a cut only if the prefix passes a test
PARTITION TREE (palindrome / word)O(2ⁿ · n) worstthe same tree, but suffixes repeat — cache 'can s[start:] split?'
PARTITION TREE + MEMOO(n²) memoisedDFS to the neighbours, mark visited cells, unmark on the way back
GRID DFS + visited marksO(R·C·4^L)one placement per row; prune any column/diagonal already attacked
CONSTRAINT PLACEMENT + PRUNEO(N!) pruned hardfirst empty cell, try each value that breaks no row/col/box, recurse
CONSTRAINT FILL + BACKTRACKexponential, prunedBacktracking is exponential, so the bound tells you it's a search problem, not a scan. Tiny n or a fixed board (Sudoku's 81 cells) says “enumerate with pruning”; a repeated subproblem says “memoise”.
SMALL n OR A FIXED BOARD ⇒ SEARCH WITH PRUNING · REPEATED SUFFIX ⇒ MEMOISE
Two partition trees, then three grids. Palindrome partitioning and Word Break share a tree (the second just memoises it); Word Search, N-Queens and Sudoku share a board. All five are deck 1's skeleton with a new choice and a new prune.
Every hard in this deck — partition, grid DFS, board fill — reduces to the same three-line skeleton. What is it?
Choose, recurse, undo — with an early prune. Palindrome partitioning chooses a cut, Word Search chooses a direction, N-Queens chooses a column, Sudoku chooses a digit; each recurses on the smaller problem and, on the way back, undoes the choice so the next sibling starts clean. The only cleverness is pruning — refusing a choice that can't lead to a solution (a non-palindrome prefix, an attacked square, an illegal digit) so the doomed subtree is never built. Once you see the skeleton, every one of these is fill-in-the-blanks.
Word Search and Sudoku both mutate a shared structure (a visited grid, the board) during recursion. What is the one discipline that keeps that correct?
Symmetric undo: every change down has a matching change up. Backtracking shares one mutable structure to avoid copying, which is fast but fragile — if a branch returns without restoring what it touched, its sibling inherits corrupted state. Mark a cell used, and unmark it when you back out; place a digit, and erase it if the recursion fails. The invariant is that a call leaves the board exactly as it received it. Copying at each node also works and is easier to reason about, but costs an extra factor of the state size.
Palindrome Partitioning is your first hard, and it is a partition tree over the string's start index. At each node you try every prefix as the next piece, but keep only the palindromic ones — a non-palindrome prefix can't begin a valid partition, so that branch is pruned. Take a valid piece, recurse on the rest, and on the way back pop it off. A path that consumes the whole string is one partition.
HOW DO YOU LIST EVERY WAY TO CUT A STRING INTO PALINDROMES?
Why is the palindrome check a prune rather than a filter applied at the leaves?
Because it kills the branch before it grows. If the current prefix isn't a palindrome, no extension of that cut can ever be a valid partition, so recursing into it only builds partitions you'll throw away. Testing isPalindrome at the node and skipping keeps the tree to exactly the valid cuts. Filtering complete partitions at the leaves is the brute force this pattern is designed to beat.
Partitioning "aab" into palindromes, how many partitions are there, and what are they?
2: [a,a,b] and [aa,b]. From start 0 the palindromic prefixes are "a" and "aa" ("aab" is not a palindrome, so that branch is pruned). Taking "a" leaves "ab", whose only palindromic prefix is "a", then "b" — giving [a,a,b]. Taking "aa" leaves "b" → [aa,b]. The visualiser strikes the pruned non-palindrome cuts in red.
Palindrome Partitioning is a partition tree over the string's start index. At each node you try every prefix cut, but keep only the ones whose prefix is a palindrome. The others are pruned, exactly as Combination Sum pruned on overshoot. Take a valid piece, recurse on the rest, and on the way back pop it off. A path that consumes the whole string is one valid partition. The only new ingredient over the deck-1 trees is the per-cut palindrome test that decides which edges exist.
“Partition a string so every piece is a palindrome” and “return all such partitions.” List-all + a per-piece validity test is the signature of a partition backtracking.
Recurse over the start index. At start, try every end position; if the prefix s[start..end] is a palindrome, add it to the current partition and recurse from end+1, then remove it (backtrack). When start passes the end, the current list is one complete partition.
// Cut at every position, but recurse only through palindrome prefixes. bool isPal(const string& s, int l, int r) { while (l < r) if (s[l++] != s[r--]) return false; return true; } void solve(int start, const string& s, vector<string>& cur, vector<vector<string>>& res) { if (start == s.size()) { res.push_back(cur); return; } // one partition for (int end = start; end < (int)s.size(); end++) { if (!isPal(s, start, end)) continue; // prune non-palindromes cur.push_back(s.substr(start, end - start + 1)); solve(end + 1, s, cur, res); // recurse on the rest cur.pop_back(); // backtrack } }
// Cut at every position, but recurse only through palindrome prefixes. boolean isPal(String s, int l, int r) { while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false; return true; } void solve(int start, String s, List<String> cur, List<List<String>> res) { if (start == s.length()) { res.add(new ArrayList<>(cur)); return; } // one partition for (int end = start; end < s.length(); end++) { if (!isPal(s, start, end)) continue; // prune non-palindromes cur.add(s.substring(start, end + 1)); solve(end + 1, s, cur, res); // recurse on the rest cur.remove(cur.size() - 1); // backtrack } }
# Cut at every position, but recurse only through palindrome prefixes. def partition(s): res, cur = [], [] def solve(start): if start == len(s): res.append(cur[:]); return for end in range(start, len(s)): piece = s[start:end + 1] if piece != piece[::-1]: continue # prune non-palindromes cur.append(piece) solve(end + 1) cur.pop() solve(0) return res
Filtering whole partitions instead of pruning cuts. Generating every cut and checking palindromity only at the end explores an exponentially larger tree — test the prefix at the node and skip non-palindromes so their subtrees are never built. Precomputing an isPal[i][j] table removes the repeated O(n) palindrome checks if the string is long.
Word Break is the same partition tree with two changes: a prefix is a legal cut only if it is a dictionary word, and the question is boolean — does any segmentation exist? Because a given start index has one fixed yes/no answer however you reach it, you memoise it — and the exponential tree collapses to O(n²). This is the bridge from backtracking to dynamic programming.
CAN THIS STRING BE SPLIT INTO DICTIONARY WORDS — AND WHY DOES CACHING MAKE IT FAST?
What makes Word Break memoisable when Palindrome Partitioning (listing all partitions) is not?
A boolean per suffix caches; an exponential list of outputs cannot. “Can s[start:] be segmented?” has one answer regardless of how you got to start, so storing it means each index is solved once — O(n²). Palindrome Partitioning must produce every partition, and there can be exponentially many, so there is nothing to shortcut in the output (you can still cache the cheap isPalindrome tests). The rule: count/exists ⇒ memoise; list-all ⇒ you're bounded by the output size.
s = "leet", dictionary {"le","et","leet"}. Does it segment, and by how many paths does the recursion find success?
Yes, via "le"+"et" or "leet". From start 0 the dictionary prefixes are "le" and "leet". "le" leaves "et", itself a word ending exactly at the string's end — success. "leet" consumes the whole string directly — also success. The boolean solver returns true the instant either completes; the visualiser shows the pruned non-dictionary prefixes (like "l", "lee") struck out.
Word Break is the same partition tree as palindrome partitioning, with the palindrome test swapped for a dictionary lookup: a prefix is a legal cut only if it is a word. A path that reaches the end is a segmentation, and the boolean answer is whether any exists, so you return true the moment one path succeeds. The killer detail is memoisation: many branches revisit the same start index, so caching “can s[start:] be broken?” collapses the exponential tree to O(n²). It is the bridge from backtracking to DP.
“Can the string be segmented into a sequence of dictionary words?” A boolean over prefix cuts with overlapping suffixes — the cue for backtracking plus memoisation.
Recurse over the start index: try each prefix, and if it is a dictionary word, recurse on the rest. Return true as soon as one path consumes the whole string. Because the same start is reached down many branches, cache its boolean answer — that turns the exponential tree into O(n²).
// Same partition tree, but boolean + memoised on the start index. unordered_set<string> dict; vector<int> memo; // -1 unknown, 0 no, 1 yes bool solve(int start, const string& s) { if (start == s.size()) return true; // consumed the whole string if (memo[start] != -1) return memo[start]; for (int end = start; end < (int)s.size(); end++) { string piece = s.substr(start, end - start + 1); if (dict.count(piece) && solve(end + 1, s)) return memo[start] = true; // one good split is enough } return memo[start] = false; // nothing works from here }
// Same partition tree, but boolean + memoised on the start index. Set<String> dict; int[] memo; // -1 unknown, 0 no, 1 yes boolean solve(int start, String s) { if (start == s.length()) return true; // consumed the whole string if (memo[start] != -1) return memo[start] == 1; for (int end = start; end < s.length(); end++) { String piece = s.substring(start, end + 1); if (dict.contains(piece) && solve(end + 1, s)) { memo[start] = 1; // one good split is enough return true; } } memo[start] = 0; // nothing works from here return false; }
# Same partition tree, but boolean + memoised on the start index. from functools import lru_cache def wordBreak(s, wordDict): words = set(wordDict) @lru_cache(None) def solve(start): if start == len(s): return True for end in range(start, len(s)): if s[start:end + 1] in words and solve(end + 1): return True return False return solve(0)
Skipping the memo — the exponential blow-up. Without caching, a string like "aaaaaaa…b" with words {a, aa, aaa…} re-solves the same suffix down countless branches, going exponential. One array keyed by start fixes it: each suffix is decided once. The other slip is a bad base case — reaching start == n means success, not failure.
Word Search moves backtracking onto a grid. From a cell matching the word's first letter, DFS to the four neighbours seeking the next letter. Mark each visited cell so the path can't reuse it; on a mismatch or a dead end, unmark it and back out. The lit path is the partial solution and the call stack is the route from the start cell to the current one.
HOW DO YOU FIND A WORD THREADED THROUGH A GRID, WITHOUT REUSING A CELL?
Why must Word Search unmark a cell (used[r][c] = false) when a branch fails, rather than leaving it marked?
Because “used” means “on the current path,” not “seen ever.” A cell is off-limits only while it's part of the path you're currently extending; when that attempt fails and you back out, the cell becomes available to other routes that might spell the word differently. Leaving it marked corrupts those sibling searches — the same symmetric-undo discipline as every backtrack. A neat O(1)-space variant overwrites the letter with a sentinel while recursing and restores it on the way back.
What is the time complexity of Word Search on an R×C grid for a word of length L, and where does it come from?
O(R·C·4^L). Any of the R·C cells can be a starting point, and from each the search fans out to up to four neighbours at every one of the L steps (three after the first, since you don't turn back), giving the 4^L factor. The used marks and the letter check prune most of that in practice, but the worst case is exponential in the word length — which is why Word Search is a backtracking problem, not a polynomial scan.
Word Search is backtracking on a grid. From a matching start cell, DFS to the four neighbours seeking the next letter; mark each visited cell so the path can't reuse it, and on a mismatch or a dead end unmark it and back out. The lit path is the partial solution and the call stack is the route from the start cell to the one you're on. It is the deck-1 skeleton, choose, recurse, undo, with the choice being a compass direction and the constraint being “matches the next letter and isn't already on the path.”
“Does the word exist in the grid along adjacent cells, no cell reused?” Search + a grid + a reuse constraint is grid DFS backtracking.
For each cell equal to the word's first letter, DFS: if the current cell matches word[k], mark it used and recurse to its four neighbours for word[k+1]; unmark on the way back. Success is matching the last letter; any mismatch or exhausted neighbour set fails that branch.
// DFS from each matching cell; mark visited, unmark on backtrack. bool dfs(vector<vector<char>>& g, const string& w, int r, int c, int k) { if (r < 0 || r >= (int)g.size() || c < 0 || c >= (int)g[0].size()) return false; if (g[r][c] != w[k]) return false; // wrong letter -> dead end if (k == (int)w.size() - 1) return true; // matched the last letter char tmp = g[r][c]; g[r][c] = '#'; // mark used (in place) bool found = dfs(g,w,r+1,c,k+1) || dfs(g,w,r-1,c,k+1) || dfs(g,w,r,c+1,k+1) || dfs(g,w,r,c-1,k+1); g[r][c] = tmp; // unmark: backtrack return found; } bool exist(vector<vector<char>>& g, string w) { for (int r = 0; r < (int)g.size(); r++) for (int c = 0; c < (int)g[0].size(); c++) if (dfs(g, w, r, c, 0)) return true; return false; }
// DFS from each matching cell; mark visited, unmark on backtrack. boolean dfs(char[][] g, String w, int r, int c, int k) { if (r < 0 || r >= g.length || c < 0 || c >= g[0].length) return false; if (g[r][c] != w.charAt(k)) return false; // wrong letter -> dead end if (k == w.length() - 1) return true; // matched the last letter char tmp = g[r][c]; g[r][c] = '#'; // mark used (in place) boolean found = dfs(g,w,r+1,c,k+1) || dfs(g,w,r-1,c,k+1) || dfs(g,w,r,c+1,k+1) || dfs(g,w,r,c-1,k+1); g[r][c] = tmp; // unmark: backtrack return found; } public boolean exist(char[][] g, String w) { for (int r = 0; r < g.length; r++) for (int c = 0; c < g[0].length; c++) if (dfs(g, w, r, c, 0)) return true; return false; }
# DFS from each matching cell; mark visited, unmark on backtrack. def exist(board, word): R, C = len(board), len(board[0]) def dfs(r, c, k): if r < 0 or r >= R or c < 0 or c >= C or board[r][c] != word[k]: return False if k == len(word) - 1: return True tmp, board[r][c] = board[r][c], '#' # mark used found = (dfs(r+1, c, k+1) or dfs(r-1, c, k+1) or dfs(r, c+1, k+1) or dfs(r, c-1, k+1)) board[r][c] = tmp # unmark: backtrack return found return any(dfs(r, c, 0) for r in range(R) for c in range(C))
Not restoring the cell after recursing. Overwriting grid[r][c] with a sentinel is a clean O(1)-space way to mark it used, but you must set it back on the way out or later paths (and other starts) see a corrupted grid. Also guard bounds and the letter check before indexing, and remember any cell can be a start.
N-Queens places one queen per row and, for each row, tries every column — pruning any column or diagonal an earlier queen already attacks. Track three sets: used columns, the ╲ diagonals keyed by row−col, and the ╱ diagonals keyed by row+col, so safe() is O(1). Place a safe queen, recurse to the next row, and if it dead-ends, lift the queen and try the next column.
HOW DO YOU PLACE N QUEENS WITH NO TWO ATTACKING — AND MAKE THE SAFETY CHECK O(1)?
Why does placing exactly one queen per row remove the need to check for row conflicts at all?
Because the structure guarantees it. solve(row) places one queen in row and recurses on row+1, so no two queens ever share a row — you get that constraint for free from the shape of the recursion. That's a common backtracking move: encode one constraint into the iteration order so you only have to actively check the others. Here it leaves just columns and the two diagonal families to guard.
On a 4×4 board, how many distinct solutions does N-Queens have, and what does the search do between them?
2 solutions. The 4×4 board admits exactly two arrangements (mirror images of each other). The solver tries columns left to right in each row; when a row offers no safe square it backtracks, removing the most recent queen and trying that row's next column. Most branches die early to pruning — the visualiser marks each attacked square in red before it is ever recursed into, which is exactly why even N=8 (92 solutions) finishes instantly.
N-Queens places one queen per row and, for each, tries every column, pruning any column, or either diagonal, that an earlier queen already attacks. Tracking the used columns and the two diagonal families (row−col and row+col) as sets makes the safe() check O(1). Place a safe queen, recurse to the next row, and if that subtree dead-ends, lift the queen and try the next column. The pruning is the whole game: cutting an attacked square removes an exponential subtree before it is ever built.
“Place N queens on an N×N board so none attack” and return all arrangements. Constraint placement, one per row, with conflict pruning — the classic backtracking.
Place one queen per row. For a row, try each column that is safe — not in a used column, nor on a used row−col or row+col diagonal — place it, recurse to the next row, then remove it. Reaching row N means a full valid board; record it.
// One queen per row; prune attacked column and both diagonals. int N; set<int> cols, d1, d2; // d1: row-col, d2: row+col vector<string> board; vector<vector<string>> res; void solve(int row) { if (row == N) { res.push_back(board); return; } for (int col = 0; col < N; col++) { if (cols.count(col) || d1.count(row-col) || d2.count(row+col)) continue; // attacked -> prune board[row][col] = 'Q'; cols.insert(col); d1.insert(row-col); d2.insert(row+col); solve(row + 1); // recurse on the next row board[row][col] = '.'; // backtrack: lift the queen cols.erase(col); d1.erase(row-col); d2.erase(row+col); } }
// One queen per row; prune attacked column and both diagonals. int N; Set<Integer> cols = new HashSet<>(), d1 = new HashSet<>(), d2 = new HashSet<>(); char[][] board; List<List<String>> res = new ArrayList<>(); void solve(int row) { if (row == N) { // a full placement List<String> snap = new ArrayList<>(); for (char[] r : board) snap.add(new String(r)); res.add(snap); return; } for (int col = 0; col < N; col++) { if (cols.contains(col) || d1.contains(row-col) || d2.contains(row+col)) continue; // attacked -> prune board[row][col] = 'Q'; cols.add(col); d1.add(row-col); d2.add(row+col); solve(row + 1); // recurse on the next row board[row][col] = '.'; // backtrack: lift the queen cols.remove(col); d1.remove(row-col); d2.remove(row+col); } }
# One queen per row; prune attacked column and both diagonals. def solveNQueens(n): res, board = [], [['.'] * n for _ in range(n)] cols, d1, d2 = set(), set(), set() # d1: r-c, d2: r+c def solve(row): if row == n: res.append([''.join(r) for r in board]); return for col in range(n): if col in cols or (row - col) in d1 or (row + col) in d2: continue # attacked -> prune board[row][col] = 'Q' cols.add(col); d1.add(row - col); d2.add(row + col) solve(row + 1) board[row][col] = '.' # backtrack cols.discard(col); d1.discard(row - col); d2.discard(row + col) solve(0) return res
Forgetting a diagonal, or not erasing the conflict keys on backtrack. Both diagonals matter — row−col for “╲” and row+col for “╱” — and each queen must remove all three keys when lifted, or later rows think squares are still attacked. Placing one queen per row already guarantees no row conflict, so don't re-check rows.
Sudoku is constraint backtracking at its purest. Find the first empty cell, try each digit 1..9, and keep only those that break no row, column or box. Place a legal digit and recurse to the next blank; if that leaves a later cell with no legal digit, the placement was wrong — erase it and try the next. “Legal right now” is not “correct”, and that gap is exactly what backtracking repairs.
HOW DO YOU FILL A SUDOKU — AND WHY ISN'T THE FIRST LEGAL DIGIT ALWAYS RIGHT?
A digit passes the row, column and box check when you place it, yet you later have to erase it. Is the checker broken?
The checker is right; local legality just isn't global correctness. legal(r,c,d) guarantees d doesn't clash with what's already on the board — it cannot know the future. A digit can satisfy every immediate constraint and still make some other blank unsolvable, and the only way to find out is to try it and recurse. When the contradiction surfaces, you erase and move to the next candidate. That try-and-undo is the whole mechanism; a puzzle that never needed it wouldn't require search at all.
Real Sudoku is 9×9. Why can a naive “first empty cell, try 1..9” backtracker still solve it quickly in practice?
Constraint pruning shrinks the branching factor to almost nothing. The full grid space is astronomically large, but at any given empty cell the row, column and box usually forbid most of 1..9, often leaving one or two candidates. So the tree the solver actually explores is a sliver of the worst case, and simple row-major order plus legality checks finishes typical puzzles fast. Choosing the most-constrained empty cell first (fewest candidates) prunes even harder — the standard speedup.
Sudoku is constraint backtracking. Find the first empty cell, try each digit 1..9, and keep only the ones that break no row, column or box. Place a legal digit and recurse to the next blank; if that leaves a later cell with no legal digit, the placement was wrong, erase it and try the next. The trap the visualiser makes concrete: “legal right now” is not “correct”, so a digit that passes every check can still be undone later. (Shown on a 4×4 for legibility; the code is the real 9×9.)
“Fill the blank cells so every row, column and 3×3 box holds 1–9.” Fill a board under constraints, backtracking on dead ends — the canonical constraint backtracking.
Find the first empty cell. Try each digit 1..9; if it breaks no row, column or box, place it and recurse. If the recursion fails (a later cell has no legal digit), erase and try the next. If no digit works, return failure so the caller backtracks. Solved when there is no empty cell left.
// First empty cell, try each legal digit, backtrack on a dead end. bool legal(vector<vector<char>>& g, int r, int c, char d) { for (int i = 0; i < 9; i++) { if (g[r][i] == d || g[i][c] == d) return false; // row, col if (g[3*(r/3) + i/3][3*(c/3) + i%3] == d) return false; // 3x3 box } return true; } bool solve(vector<vector<char>>& g) { for (int r = 0; r < 9; r++) for (int c = 0; c < 9; c++) if (g[r][c] == '.') { for (char d = '1'; d <= '9'; d++) { if (!legal(g, r, c, d)) continue; // clashes -> skip g[r][c] = d; // place & recurse if (solve(g)) return true; g[r][c] = '.'; // dead end -> erase } return false; // no digit -> backtrack } return true; // no empty cell -> solved }
// First empty cell, try each legal digit, backtrack on a dead end. boolean legal(char[][] g, int r, int c, char d) { for (int i = 0; i < 9; i++) { if (g[r][i] == d || g[i][c] == d) return false; // row, col if (g[3*(r/3) + i/3][3*(c/3) + i%3] == d) return false; // 3x3 box } return true; } boolean solve(char[][] g) { for (int r = 0; r < 9; r++) for (int c = 0; c < 9; c++) if (g[r][c] == '.') { for (char d = '1'; d <= '9'; d++) { if (!legal(g, r, c, d)) continue; // clashes -> skip g[r][c] = d; // place & recurse if (solve(g)) return true; g[r][c] = '.'; // dead end -> erase } return false; // no digit -> backtrack } return true; // no blanks left }
# First empty cell, try each legal digit, backtrack on a dead end. def solveSudoku(board): def legal(r, c, d): for i in range(9): if board[r][i] == d or board[i][c] == d: return False if board[3*(r//3) + i//3][3*(c//3) + i%3] == d: return False return True def solve(): for r in range(9): for c in range(9): if board[r][c] == '.': for d in '123456789': if not legal(r, c, d): continue board[r][c] = d # place & recurse if solve(): return True board[r][c] = '.' # backtrack return False # no digit works here return True # solved solve()
Treating “legal now” as final, or returning the wrong base case. A digit that passes the row/column/box check can still be wrong — you only learn that when a later cell has no option, so you must erase and try the next. And “no empty cell” means solved (return true); returning false there breaks the whole recursion. Scanning for the most-constrained cell first is the standard speedup.
Palindrome Partitioning enumerates ALL partitions; Word Break only asks whether ONE segmentation exists. How does that change the code, and the complexity?
“All” forces you to visit every leaf; “does one exist” lets you stop early and cache. When the answer is a boolean, a given start index has a fixed yes/no answer regardless of how you reached it, so memoising it collapses the exponential tree to O(n²) — the same suffix is never re-explored. Palindrome Partitioning can't memoise the output the same way (it must list every partition, which is exponentially many), though it can still cache the palindrome tests. Recognising “count/list all” versus “does one exist” is what tells you whether DP is even available.
In N-Queens the safe() check is made O(1) by tracking three sets. Which three, and why do the diagonals reduce to a single number each?
Columns, plus the two diagonal families keyed by row−col and row+col. Placing one queen per row makes rows automatic; a column is attacked if it's in the used-columns set. The elegance is the diagonals: every square on a “╲” diagonal has the same row − col, and every square on a “╱” diagonal the same row + col, so each diagonal is one integer key in a set. That turns the conflict test into three O(1) lookups, and the pruning it enables is what makes N-Queens finish.
Hard-backtracking bugs pass the sample and corrupt the rest: a missing undo, a lost memo, a forgotten diagonal, a prune that fires too late. Every one compiles and returns a believable answer.
Mark a cell / place a queen / write a digit going down, and you MUST unmark / remove / erase coming back. A branch that returns without restoring the shared board corrupts every sibling. The push and the pop must bracket the recursive call exactly.
In Sudoku a digit that breaks no row/column/box right now can still strand a later cell with no option. That is not a bug to avoid — it is why you backtrack. Never assume the first legal value is final.
Word Break's naive recursion is exponential because the same suffix s[start:] is re-solved down many branches. Cache the boolean answer per start and it becomes O(n²). Palindrome Partitioning can't cache the output, but can cache the isPalindrome tests.
Word Search must mark a cell before recursing and unmark after, or a later branch treats it as free and a path illegally reuses the same square. Temporarily overwriting the letter (then restoring it) is a common O(1)-space trick — just restore it.
Miss a diagonal family and two queens end up diagonal to each other. The keys are row − col (which can be negative — offset it, or use a map) and row + col. Testing only one diagonal, or reusing the column key for it, silently admits illegal boards.
Placing a value and only discovering its illegality at a leaf still builds the whole dead subtree. Test the constraint before the recursive call (a non-palindrome prefix, an attacked square, an illegal digit) so the branch is never entered — that early cut is the difference from brute force.
Five hards, one page. The right-hand column is the choice-and-prune — the shape of the tree or grid that should come to mind the instant you read the statement.
Partition a string, thread a word through a grid, place queens, fill a Sudoku — every one was choose, recurse, undo, with a prune that kills the dead branches early. The only new idea beyond deck 1 was memoising the boolean partition (Word Break) — the doorway to dynamic programming, which is the next step of the sheet.
No lecture playlist was supplied, so this deck is problems, drills and visualisers — no concept videos. All five problems are LeetCode. Sudoku and N-Queens are animated on a 4×4 board for legibility; the code is the real 9×9 / N×N.
Not a preference — an arithmetic one. Every slide is a fixed 1280 × 720 stage: a graph animating beside the code that drives it, with the problems laid out two columns wide. It scales as a single piece, so on a screen this size the body text comes out around 4px tall.
Shrinking it further would not help, and rebuilding it to reflow would mean losing the thing that makes it worth reading.