Backtracking — Master Notes (Combined)

Practical, interview-focused. Zero fluff theory, maximum application. Combines Hinglish quick-recall notes with detailed
English explanations.

1. First Principles

How to Recognize a Backtracking Problem

Quick signals (Hinglish):

"All possible ways/combinations/permutations": Agar question bole return all valid combinations, subsets, ya paths.

Constraint Satisfaction: Ek specific arrangement dhoondni hai jo strict rules follow kare (Sudoku, N-Queens).

Exponential limits: Constraints dekho. Agar N ≤ 20, toh maximum chances hain ki O(2^N) ya O(N!) wali
backtracking lagegi.

Detailed signal list:

"generate all valid answers"

"find one valid answer with constraints"

"count / list combinations, permutations, subsets, partitions"

"explore a state space"

"try many choices, then undo and try another"

"satisfy rules, limits, or uniqueness"

Trigger phrases to watch for:

"all possible", "print every", "find combinations", "arrange", "path in maze", "valid arrangement", "no duplicate", "exact
target", "can place / can choose / can partition"

Recursion vs DFS vs Brute Force vs Backtracking

Term Meaning

Recursion Mechanism — a function calling itself.

DFS Traversal style — explore one branch fully before another / ghusna till the end.

Brute Force Try all possibilities blindly, even bad ones.

"Smart Brute Force" — go down a path; if it hits a dead end or invalid condition, undo and go back without
Backtracking
traversing the full path (Pruning).

In interview language: recursion is the tool, DFS is the traversal style, brute force is the search space, backtracking is the
optimized search strategy (brute force + early rejection + undoing state).
Exact Thinking Process (Before Coding)

Ask these questions every time, in order:

1. What am I trying to build? — Output format kya hai? (2D vector, single string, answer list, one answer, count,
boolean, etc.)

2. What is the current state? — Current index, path, remaining target, visited, board position.

3. What choices do I have right now? — Element ko lu ya chhodu? Pick/skip/place/move/swap/partition. Kahan place
karu?

4. What is invalid? — Out of bounds, duplicate, sum too big, rule broken.

5. What is the base case / Goal? — Kahan rukna hai? When do I stop and store the answer?

6. What must be undone? — Path changes, visited marks, swaps, chosen elements.

The universal loop:

state → choices → validate → do → recurse → undo

2. State Identification

What is the state?

Ek recursion tree ke kisi node ko "State" bolte hain — the current snapshot of your progress (current index, current sum,
current temp path). It answers: "What information changes while recursion goes deeper?"

Examples: current index, current path/partial answer, remaining sum/target, visited array, board configuration, current
cell in grid, used-numbers mask.

What changes during recursion?

index (aage badhne ke liye)

current_sum / remaining_target

temp_vector / path (grows/shrinks)

visited array/board

counts / mask

What remains constant?

Main input array/string ( nums , s )

Original target value

Grid dimensions

Constraint definitions

ans vector / answer container reference

What to pass as parameters (and how)

 Pass by Value Pass by Reference (&)

Primitive types that must differ per branch: Heavy/shared structures: vector<int>& nums , vector<int>&
index , current_sum , small counts/masks temp , vector<vector<int>>& ans , board, visited matrix

Use when state is small and an independent Use when the object is shared + modified + must be undone — avoids
copy is conceptually simpler (no undo needed) O(N) copy time/space per call

Practical rule: if the object is shared + modified + undone → pass by reference. If it's small + independent copy is fine
→ pass by value.

Never pass unnecessarily:

Globally-fixed values that don't need re-passing (but avoid true global variables in competitive programming
anyway — pass constants by reference instead)

Full copied arrays/vectors/boards every call when a reference would do

Common per-pattern parameter sets:

Subsets / combinations: index , path

Permutations: index , nums , used[] (or swap-based index only)

Grid traversal: i , j , visited , path

Sudoku / N-Queens: board , row/col/diagonal trackers

Partitioning: start index , path

Expression generation: index , expr , current value , last operand

3. Decision Tree Checklist

Run this checklist on every new problem:

1. Choices — Current index/state par main kya action le sakta hu? (Pick/Not Pick, 1 to 9 numbers, 4 directions,
place/move/swap/cut/add-operator)

2. Constraints — Kya ye choice allowed hai? (e.g. remaining sum < 0 → invalid; placement conflicts; out of grid;
substring not palindrome)

3. Goal / Base Case — Result kab store karna hai? (index == n, target == 0, full permutation built, board filled,
destination reached)

Two types of base case:

1. Success base case → store answer and return

2. Failure base case → stop the invalid branch immediately

4. Pruning — Kab branch turant kill karni hai? (sorted array + current element already > remaining target → break;
duplicate branch already explored; sum too large; unsafe cell; row/col/diag conflict)

5. Undo Operation — Agar temp.push_back() kiya recursion se pehle, wapas aate time temp.pop_back() karna hi
padega. Similarly: visited[i][j] = false , re- swap() , restore board cell.

Extended universal checklist (10-point version):

 1. What is the answer type?

2. What is the state?

3. What are the choices?

4. What is invalid?

5. What is the goal?

6. What is the base case?

7. What must be undone?

8. Do I need pruning?

9. Do I need duplicate handling?

10. Do I need sorting or ordering?

4. Every Backtracking Pattern

Pattern A — Pick / Don't Pick (Subsets)

Used for: power sets, all subsequences, 0/1 knapsack-style decisions.

Recognize it when: every element gets exactly two decisions (include/exclude), order doesn't matter, each element
considered once.

Thinking: Har index wale element se pucho: "Tujhe temp mein aana hai ya nahi?"

void solve(int i, vector<int>& nums, vector<int>& path, vector<vector<int>>& ans) {

if (i == [Link]()) {
ans.push_back(path);
return;
}

// pick
path.push_back(nums[i]);
solve(i + 1, nums, path, ans);
path.pop_back();

// don't pick
solve(i + 1, nums, path, ans);
}

Dry run for [1,2] : pick1→pick2, pick1→skip2, skip1→pick2, skip1→skip2.

Complexity: Time O(2^N) , Space O(N) (call stack + path).

Common mistakes: forgetting base case, missing undo, using a loop unnecessarily.

LeetCode: 78. Subsets, 90. Subsets II.

Pattern B — For-loop Expansion (Combinations / Permutations base)

Used for: Combination Sum, Permutations, placing items in K slots, subsets with controlled order.
Recognize it when: one recursion level chooses from many candidates using a start index; order among chosen
items shouldn't repeat.

Thinking: Ek fixed position ke liye N elements choices hain — loop i se N tak chalao.

void solve(int index, vector<int>& nums, vector<int>& temp, vector<vector<int>>& ans) {

ans.push_back(temp); // base case depends on problem — here every prefix collected

for (int i = index; i < [Link](); i++) {

// Pruning: skip duplicates
if (i > index && nums[i] == nums[i-1]) continue;

temp.push_back(nums[i]); // DO
solve(i + 1, nums, temp, ans); // RECURSE (use i instead of i+1 if reuse allowed)
temp.pop_back(); // UNDO
}
}

Duplicates handling: if array sorted and nums[i] == nums[i-1] , continue to avoid duplicate subsets.

Complexity: O(N!) or O(K · C(N,K)) , Space O(N) .

Common mistakes: using i+1 vs start+1 incorrectly, missing duplicate skip, confusing combination with
permutation logic.

LeetCode: 39. Combination Sum, 46. Permutations.

Pattern C — Permutations (order matters)

Used for: arrangements of all elements, all orderings of a set.

Recognize it when: same set, different ordering; each element used exactly once per arrangement; needs visited[]
or swap technique.

Template 1 — visited array:

void solve(vector<int>& nums, vector<int>& path, vector<int>& used, vector<vector<int>>& ans) {

if ([Link]() == [Link]()) {
ans.push_back(path);
return;
}
for (int i = 0; i < [Link](); i++) {
if (used[i]) continue;
used[i] = 1;
path.push_back(nums[i]);
solve(nums, path, used, ans);
path.pop_back();
used[i] = 0;
}
}

Template 2 — swap method (O(1) extra space):

 void solve(int index, vector<int>& nums, vector<vector<int>>& ans) {
if (index == [Link]()) {
ans.push_back(nums);
return;
}
for (int i = index; i < [Link](); i++) {
swap(nums[index], nums[i]); // DO
solve(index + 1, nums, ans); // RECURSE
swap(nums[index], nums[i]); // UNDO
}
}

Complexity: Time O(N! · N) , Space O(N) .

Common mistakes: forgetting used[i] = 0 , generating duplicate permutations, confusing with combinations.

LeetCode: 46. Permutations, 47. Permutations II.

Pattern D — Combinations (order doesn't matter, size may be fixed)

Used for: choosing exactly k items, group building, non-order-sensitive selection.

Recognize it when: order irrelevant, start index matters, k often given explicitly.

void solve(int start, int k, vector<int>& nums, vector<int>& path, vector<vector<int>>& ans) {
if ([Link]() == k) {
ans.push_back(path);
return;
}
for (int i = start; i < [Link](); i++) {
path.push_back(nums[i]);
solve(i + 1, k, nums, path, ans);
path.pop_back();
}
}

Complexity: Time O(C(N,K)) , Space O(K) .

Common mistakes: using a permutation template, incorrect base case, forgetting the k stop condition.

LeetCode: Combinations, Combination Sum, Combination Sum II.

Pattern E — Subsets (all sizes, combination-style)

Used for: all subsets/prefixes, including the empty set.

Recognize it when: every element included or not, answer count is 2^N .

void solve(int start, vector<int>& nums, vector<int>& path, vector<vector<int>>& ans) {

ans.push_back(path);
for (int i = start; i < [Link](); i++) {
 path.push_back(nums[i]);
solve(i + 1, nums, path, ans);
path.pop_back();
}
}

Common mistakes: forgetting to include the empty subset, missing duplicate handling.

LeetCode: Subsets, Subsets II.

Pattern F — K Selections

Used for: picking exactly k elements — fixed-size groups (Combination Sum III, k-subsets).

Thinking: if [Link]() == k , store the answer; otherwise choose from remaining candidates.

LeetCode: Combinations, Combination Sum III.

Pattern G — Duplicate Handling

Used when: input has repeated values and answers must stay unique (Subsets II, Combination Sum II, Permutations
II).

Core rule: Sort the array first.

Skipping rule:

if (i > start && nums[i] == nums[i - 1]) continue;

This prevents exploring the same value at the same decision level more than once — it kills ~50% of duplicate
branches before they even start (constraint propagation).

For permutations with duplicates: skip if nums[i]==nums[i-1] && !used[i-1] .

Common mistakes: skipping duplicates at the wrong level, not sorting, incorrect skip logic in permutations.

Pattern H — Target Sum / Sum-Constrained Search

Used for: Combination Sum, Subset Sum, target count, exact-value selection.

Recognize it when: problem mentions "target", "sum", "remaining"; must hit exact value; overshoot can be pruned.

void solve(int start, int target, vector<int>& nums, vector<int>& path, vector<vector<int>>& ans)
{
if (target == 0) {
ans.push_back(path);
return;
}
if (target < 0) return;
 for (int i = start; i < [Link](); i++) {
path.push_back(nums[i]);
solve(i, target - nums[i], nums, path, ans); // i → reuse allowed; i+1 → no reuse
path.pop_back();
}
}

Sorting + Bounding: sort array first — if current_sum + nums[i] > target , then break the loop instead of recursing
further (all subsequent elements will also overshoot).

Common mistakes: wrong start value for reuse vs non-reuse, forgetting target pruning, missing duplicate handling.

LeetCode: Combination Sum, Combination Sum II, Target Sum.

Pattern I — Partitioning

Used for: cutting a string/array into valid chunks (Palindrome Partitioning, Restore IP Addresses).

Recognize it when: "partition string", cut positions matter, each segment has a validity rule.

Thinking: current index is start ; loop end from start to string-end; if substring(start, end) is valid, add it to
the path and recurse from end + 1 .

void solve(int start, string& s, vector<string>& path, vector<vector<string>>& ans) {

if (start == [Link]()) {
ans.push_back(path);
return;
}
for (int end = start; end < [Link](); end++) {
if (isValid(s, start, end)) {
path.push_back([Link](start, end - start + 1)); // DO
solve(end + 1, s, path, ans); // RECURSE
path.pop_back(); // UNDO
}
}
}

Common mistakes: wrong substring indices, checking validity too late, missing base case.

LeetCode: 131. Palindrome Partitioning, 93. Restore IP Addresses, Word Break (partitioning mindset).

Pattern J — Grid Traversal (DFS + Backtrack)

Used for: mazes, flood fill, path finding, Word Search, all routes in a matrix.

Recognize it when: 2D board, moves in 4 (or 8) directions, visited needed to avoid cycles.

Thinking: har cell se 4 directions (i+1,j) , (i-1,j) , (i,j+1) , (i,j-1) . Mark visited before going, un-mark on the
way back so other paths can reuse that cell.
 void solve(int i, int j, vector<vector<int>>& grid, vector<vector<int>>& vis, string& path,
vector<string>& ans) {
if (i == [Link]() - 1 && j == grid[0].size() - 1) {
ans.push_back(path);
return;
}
vis[i][j] = 1;
for (auto [di, dj, ch] : moves) {
int ni = i + di, nj = j + dj;
if (isSafe(ni, nj, grid, vis)) {
path.push_back(ch);
solve(ni, nj, grid, vis, path, ans);
path.pop_back();
}
}
vis[i][j] = 0;
}

Common mistakes: forgetting to reset visited, wrong boundary check, infinite loops.

LeetCode: Rat in a Maze, Flood Fill, Unique Paths III.

Pattern K — Word Search (specific grid traversal + string match)

Used for: matching a word inside a board via adjacent moves, without reusing a cell.

State: board position, current word index, visited state (often done in-place by marking the board cell itself).

bool solve(int i, int j, vector<vector<char>>& board, string& word, int index) {

if (index == [Link]()) return true; // found the word

if (i < 0 || i >= [Link]() || j < 0 || j >= board[0].size() || board[i][j] != word[index])

return false;

char temp = board[i][j];

board[i][j] = '*'; // DO: mark visited in place

bool found = solve(i+1, j, board, word, index+1) ||

solve(i-1, j, board, word, index+1) ||
solve(i, j+1, board, word, index+1) ||
solve(i, j-1, board, word, index+1);

board[i][j] = temp; // UNDO: restore original character

return found;
}

Common mistakes: forgetting to restore the board/visited cell, matching the wrong character index, not stopping once
the full word is found.

LeetCode: 79. Word Search, 212. Word Search II.

Pattern L — Graph Traversal with Backtracking

Used for: exploring all simple paths / all valid routes in a graph.

Recognize it when: graph input, "all paths", no revisiting nodes within the same path, path enumeration.

Thinking: node is the state; mark visited within the current path; recurse into neighbors; undo the visited mark on
return.

LeetCode: All Paths From Source to Target, Hamiltonian Path-style problems.

Pattern M — Constraint Satisfaction

Used for: structures that must satisfy many simultaneous rules (Sudoku, N-Queens, M-Coloring).

Thinking: choose a cell → try a candidate → check row/col/diag/box (or adjacency) constraints via isValid() →
recurse → undo.

LeetCode: N-Queens, Sudoku Solver, M-Coloring Problem.

Pattern N — N-Queens (special constraint placement)

State: current row, columns used, diagonals used, anti-diagonals used.

void solve(int row, int n, vector<string>& board,

vector<int>& col, vector<int>& diag, vector<int>& anti, vector<vector<string>>& ans) {
if (row == n) {
ans.push_back(board);
return;
}
for (int c = 0; c < n; c++) {
if (col[c] || diag[row + c] || anti[row - c + n - 1]) continue;

board[row][c] = 'Q';
col[c] = diag[row + c] = anti[row - c + n - 1] = 1;

solve(row + 1, n, board, col, diag, anti, ans);

board[row][c] = '.';
col[c] = diag[row + c] = anti[row - c + n - 1] = 0;
}
}

Common mistakes: wrong diagonal index formula, missing undo, placing more than one queen per row.

LeetCode: N-Queens, N-Queens II.

Pattern O — Sudoku (constraint-heavy board filling)

State: board, current empty-cell index, row/col/box trackers. Fill 1–9 in each empty cell, validating row, column, and
3×3 box before recursing.

LeetCode: Sudoku Solver.

Pattern P — Palindrome Partitioning (specific instance of Pattern I)

State: start index, path of substrings. Pruning: skip immediately if the substring isn't a palindrome.

LeetCode: Palindrome Partitioning.

Pattern Q — Expression Generation

Used for: inserting operators ( + - * ) between digits and evaluating on the fly (Expression Add Operators).

State: current index, current expression string, current running value, last operand (needed to correctly undo/handle
multiplication precedence).

Thinking: at each step, extend the current number or choose an operator, updating the running total; take care with *
since it needs the last operand to "undo" the previous addition.

LeetCode: Expression Add Operators.

Pattern R — General Fallback

Any other interview variant still reduces to the same base loop: choose from multiple candidates → obey constraints
→ recurse → undo → prune.

5. Pruning (Branch Killing in Depth)

Pruning = cutting useless recursive branches early to avoid TLE (Time Limit Exceeded).

Core idea: if one branch is impossible, every child of that branch is also impossible — so pruning saves exponential
work.

Sorting + Bounding: Array ko pehle sort kar lo. E.g. target = 10, current sum = 8. If next element is 5 (8+5=13>10), all
subsequent elements (being ≥5 after sorting) will also overshoot — break the loop instead of recursing further.

Duplicate Skipping (Constraint Propagation): in a sorted array, if (i > start_index && nums[i] == nums[i-1])
continue; — kills ~50% of duplicate branch trees before they even start.

Early Return: if only a true/false answer is needed (e.g. "is Sudoku solvable"), return true immediately up the call
stack as soon as one valid answer is found — don't wait to collect into ans .

Practical pruning checklist:

Can I stop because the target is already impossible? ( target < 0 )

Can I skip a duplicate branch at the same level?

 Can I reject an invalid placement immediately (bounds/row/col/diag)?

Have I already tried this same state?

Can sorting the input help me prune faster?

Can I precompute/propagate constraints as I go (update visited, mark rows/cols/diagonals, subtract target)

instead of checking only at the end?

6. Recursion Tree & the DO → RECURSE → UNDO Rhythm

Pick/Don't-Pick tree for [1, 2] :

[ ] (index=0)
/ \
(Pick 1) / \ (Don't Pick 1)
[1] [ ] (index=1)
/ \ / \
(P 2) / (DP 2) (P 2) (DP 2)
[1,2] [1] [2] [ ] (index=2 -> Base Case Hit!)

For-loop expansion tree (shape):

start
├─ choose 1
│ ├─ choose 2
│ └─ choose 3
├─ choose 2
└─ choose 3

Permutation tree (shape): each level tries every still-unused element, branching into all remaining orderings before
returning back up.

The universal flow behind every template above:

1. temp.push_back(x) → DO

2. solve(...) → RECURSE

3. temp.pop_back() → UNDO (state restored exactly as it was before step 1)

7. Template Library (C++) — Quick Reference

Template 1 — For-loop Backtracking (Combination Sum / Subsets II):

void solve(int index, vector<int>& nums, vector<int>& temp, vector<vector<int>>& ans) {

ans.push_back(temp);
for (int i = index; i < [Link](); i++) {
if (i > index && nums[i] == nums[i-1]) continue;
temp.push_back(nums[i]);
solve(i + 1, nums, temp, ans); // use i instead of i+1 if reuse allowed
temp.pop_back();
 }
}

Template 2 — Permutations via Swaps (O(1) extra space):

void solve(int index, vector<int>& nums, vector<vector<int>>& ans) {

if (index == [Link]()) { ans.push_back(nums); return; }
for (int i = index; i < [Link](); i++) {
swap(nums[index], nums[i]);
solve(index + 1, nums, ans);
swap(nums[index], nums[i]);
}
}

Template 3 — String Partitioning (Palindrome Partitioning):

void solve(int index, string& s, vector<string>& temp, vector<vector<string>>& ans) {

if (index == [Link]()) { ans.push_back(temp); return; }
for (int i = index; i < [Link](); ++i) {
if (isPalindrome(s, index, i)) {
temp.push_back([Link](index, i - index + 1));
solve(i + 1, s, temp, ans);
temp.pop_back();
}
}
}

Template 4 — Grid DFS with Backtracking (Word Search):

bool solve(int i, int j, vector<vector<char>>& board, string& word, int index) {

if (index == [Link]()) return true;
if (i < 0 || i >= [Link]() || j < 0 || j >= board[0].size() || board[i][j] != word[index])
return false;
char temp = board[i][j];
board[i][j] = '*';
bool found = solve(i+1, j, board, word, index+1) ||
solve(i-1, j, board, word, index+1) ||
solve(i, j+1, board, word, index+1) ||
solve(i, j-1, board, word, index+1);
board[i][j] = temp;
return found;
}

8. Pattern Recognition — 50 Interview Problems

Scan this table whenever a new question appears — identify the pattern before writing code.
 State
# Problem Name Pattern Choices Pruning / Base Case
(Params)

1 Subsets Pick/Not Pick idx Include/Exclude idx == N

2 Subsets II For-loop idx Pick nums[i] Skip duplicates if(i>idx)

3 Permutations Swap idx Swap idx with i idx == N

idx, visited Skip if num[i]==num[i-1]

4 Permutations II Swap + Visited Place unused val
array & !vis[i-1]

5 Combination Sum For-loop idx, target Pick same nums[i] target < 0 (Prune)

Combination Sum Sort & skip duplicates,

6 For-loop idx, target Pick next nums[i]
II target < 0

Combination Sum
7 For-loop k, target, num Pick 1 to 9 k == 0 check target
III

8 Combinations For-loop idx, k Pick 1 to N [Link]() == k

Letter
9 For-loop idx of digits Chars of digit[i] idx == [Link]()
Combinations

Palindrome Only recurse if

10 Partitioning idx Substring [idx...i]
Partition isPalindrome()

Take 1, 2, or 3 val > 255 or leading

11 Restore IP Partitioning idx, dots
chars zero

12 Word Break II Partitioning idx Prefix in dict? Reached end of string

isValid() col, diag, anti-

13 N-Queens Constraint row Place Q in col
diag

isValid() row, col, 3x3

14 Sudoku Solver Constraint row, col Fill 1 to 9
block

Out of bounds, board[i]

15 Word Search Grid DFS i, j, word_idx 4 directions
[j] != char

Path with Max

16 Grid DFS i, j, curr_gold 4 directions board[i][j] == 0
Gold

Out of bounds, visited,

17 Rat in a Maze Grid DFS i, j, path_str D, L, R, U
wall

Generate open > n or close >

18 Decision Tree open, close Add ( or )
Parentheses open

Place match in 1 of
19 Matchsticks to Sq Target Sum idx, sides[4] side > target / Sort desc
4
 State
# Problem Name Pattern Choices Pruning / Base Case
(Params)

Partition K idx, k, Add to current curr_sum > target,

20 Target Sum
Subsets curr_sum bucket visited array

Substring to
21 Splitting a String Partitioning idx, prev_val num != prev_val - 1
number

Beautiful i % num == 0 or num % i

22 Permutations idx, count Place valid num
Arrangement == 0

23 Valid Sudoku Iterative Grid cells Check constraints Row/Col/Box hashsets

Diff Ways to
24 Partitioning left, right Split at operators Return evaluated list
Compute

Optimal Account
25 Constraint idx Settle debt with i Skip if opposite signs
Bal

Factor
26 For-loop n, start_factor Divisors of n n % i != 0
Combinations

Obstacles, empty_cnt !=
27 Unique Paths III Grid DFS i, j, empty_cnt 4 directions
0

Max Length Overlapping characters

28 Pick/Not Pick idx, curr_str Include string
Concated (bitmask)

Missing intermediate
29 Android Unlock Grid DFS curr, len Next digit 1-9
numbers

Subset Sums
30 Pick/Not Pick idx, sum Add/Don't Add idx == N
(GFG)

M-Coloring isValid() adj nodes

31 Constraint node Assign color 1-M
Problem color

32 Hamiltonian Path Graph Traversal node, count Unvisited neighbors count == V

idx, curr_sum,
33 Tug of War Subset/Diff Assign to Set 1/2 Maintain N/2 size limit
cnt

34 Find Paths in Grid Grid DFS i, j, k (turns) 4 dirs k < 0, bounds

35 Knight Tour Grid Traversal i, j, move_no 8 knight moves move_no == N*N

Remove Invalid
36 Graph/BFS+Backtrack str Remove ( or ) Valid parenthesis check
Par.

Expression Add Handle multiplication

37 Partitioning idx, prev_num Add +, -, *
Ops precedence
 State
# Problem Name Pattern Choices Pruning / Base Case
(Params)

38 Scramble String Partitioning s1, s2 Split at i Memoization / Pruning

39 ZUMA Game Simulation board, hand Insert ball Board collapses

Target = 24 within
40 24 Game Simulation array size 4 Pick 2, apply ops
epsilon

41 Stickers to Spell For-loop target, freq Apply sticker chars Bitmask state pruning

Regular Exp
42 Pick/Not Pick i, j Match * or . String lengths
Match

Wildcard
43 Pick/Not Pick i, j Treat * as 0 or N String lengths
Matching

Assign unassigned Manhattan dist,

44 Campus Bikes II Permutations worker_idx
bike Bitmask vis

Confusing
45 For-loop curr_num Append 0,1,6,8,9 num > N
Number II

One-to-one mapping
46 Word Pattern II Partitioning idx_s, idx_p Map char to substr
breaks

Return excess
47 Distribute Coins Tree Backtrack node Base case: Null
coins

Gen all Filter valid time

48 Largest Time Permutations array
permutations hours/mins

Check freq array of

49 Max Score Words Subsets idx Include word
letters

Leading zero, column

50 Verbal Arithmetic Constraint char_idx, digit Assign 0-9 to char
sum

9. Common Mistakes (Interview Killers)

Missing UNDO ( pop_back() ): C++ arrays/vectors get modified in place. If not un-modified, the next branch
inherits the previous branch's leftover state.

Passing by Value in recursion: passing vector<int> temp (no & ) copies the vector at every recursion depth —
turns O(2^N) into O(N · 2^N) and risks MLE (Memory Limit Exceeded).

Wrong Base Case: forgetting return when the goal is met → infinite recursion → segmentation fault.

Global Variables Mess: e.g. a global visited matrix not cleared before the next test case.

String Pass by Value vs Reference: temp + char passed by value makes C++ create a new string each time
(auto-copies and auto-undoes). If string& temp is passed by reference instead, you must explicitly pop_back()
 to undo.

10. Master Cheat Sheet

Recognition flowchart:

1. Is it asking for all paths/configurations? → Backtracking.

2. Can elements be reused? → Yes: pass i . No: pass i + 1 .

3. Does order matter? → Yes (Permutations): loop i = 0 . No (Combinations): loop i = index .

4. Are there duplicate elements? → Sort the array → if (i > index && nums[i] == nums[i-1]) continue;

Pre-run debugging checklist:

[ ] Base case present?

[ ] Base case ends with return ?

[ ] Constraints checked before entering RECURSE?

[ ] UNDO operation exactly mirrors the DO operation?

[ ] Data structures passed by reference ( & )?

Dry-run trick: always take N = 3 as input and trace the first branch all the way to the base case, then step back up
one level and try the second path. Doing this on paper makes the code's structure completely clear before you type it.