Chapter 11a — Backtracking Problems
The Five Problem Types
Every problem here maps to one of three templates from Chapter 11:
| Template | Starting index start | Reuse same element? | Sort needed? |
|---|---|---|---|
| Subsets | advances | No | For dedup only |
| Combination (unique) | advances | No | Yes, for dedup |
| Combination (reuse) | stays | Yes | Yes, for pruning |
| Permutation | ignored | No, use used[] | For dedup only |
| Grid DFS | grid coordinates | No, use mark | No |
Before reading each problem, ask: what is the shape of the decision tree?
Problem 1: Subsets II (with duplicates)
LeetCode 90
Given an array that may contain duplicates, return all subsets without duplicate subsets.
What do I have? nums = [1, 2, 2].
What do I want? All unique subsets: [[], [1], [1,2], [1,2,2], [2], [2,2]].
Brute force? Generate all subsets, put them in a Set (requires sorting each to compare). O(2^n × n log n).
Where is waste? When considering position i in the loop, if nums[i] === nums[i-1] and we're at the same tree level (same start), we're about to generate the exact same subtree we already explored. Skip it.
function subsetsWithDup(nums) {
nums.sort((a, b) => a - b); // MUST sort first
const result = [];
function backtrack(start, current) {
result.push([...current]);
for (let i = start; i < nums.length; i++) {
// Skip duplicate at the same level
if (i > start && nums[i] === nums[i - 1]) continue;
current.push(nums[i]);
backtrack(i + 1, current);
current.pop();
}
}
backtrack(0, []);
return result;
}
Full dry run on [1, 2, 2] (after sort: [1, 2, 2]):
backtrack(0, []) → collect []
i=0: push 1 → backtrack(1, [1]) → collect [1]
i=1: push 2 → backtrack(2, [1,2]) → collect [1,2]
i=2: push 2 → backtrack(3, [1,2,2]) → collect [1,2,2], done
pop 2
pop 2
i=2: i>start (2>1) AND nums[2]===nums[1] (2===2) → SKIP
pop 1
i=1: push 2 → backtrack(2, [2]) → collect [2]
i=2: push 2 → backtrack(3, [2,2]) → collect [2,2], done
pop 2
pop 2
i=2: i>start (2>0) AND nums[2]===nums[1] (2===2) → SKIP
Result: [[], [1], [1,2], [1,2,2], [2], [2,2]]. ✓
Why does sorting enable deduplication? After sorting, equal elements are adjacent. When we skip nums[i] === nums[i-1] at the same level, we're skipping the second identical choice at that fork of the tree. If we didn't sort, equal elements could be scattered and this simple check wouldn't work.
Problem 2: Combination Sum (unlimited reuse)
LeetCode 39 — asked at Zepto, Razorpay
Given candidates [2, 3, 6, 7] and target 7, find all unique combinations that sum to 7. Same number may be used unlimited times.
The full solution and dry run appear in Chapter 11 §6. Here we extend to understand why the complexity is what it is.
function combinationSum(candidates, target) {
const result = [];
candidates.sort((a, b) => a - b);
function backtrack(start, current, remaining) {
if (remaining === 0) { result.push([...current]); return; }
for (let i = start; i < candidates.length; i++) {
if (candidates[i] > remaining) break; // prune: sorted, so all later > remaining too
current.push(candidates[i]);
backtrack(i, current, remaining - candidates[i]); // i, not i+1: allow reuse
current.pop();
}
}
backtrack(0, [], target);
return result;
}
The "i not i+1" insight: When we call backtrack(i, ...) we're saying "on the next level, I can still pick candidates[i] again." This is what enables [2, 2, 3] — the 2 is picked at level 1, and at level 2 we start from i=0 again, picking 2 again.
When we call backtrack(i+1, ...) we'd be saying "move past candidates[i] — never pick it again." That's the Combination Sum II behavior.
Problem 3: Combination Sum II (limited reuse, with duplicates)
LeetCode 40
Given candidates [10, 1, 2, 7, 6, 1, 5] and target 8, find combinations that sum to 8. Each number may only be used once. Input may have duplicates.
What do I have? Array with possible duplicates, target.
What do I want? Unique combinations summing to target, each element used at most once.
Difference from Problem 2? Two changes: i+1 instead of i (no reuse), and skip-duplicate check (input has duplicates).
function combinationSum2(candidates, target) {
candidates.sort((a, b) => a - b);
const result = [];
function backtrack(start, current, remaining) {
if (remaining === 0) { result.push([...current]); return; }
for (let i = start; i < candidates.length; i++) {
if (candidates[i] > remaining) break;
if (i > start && candidates[i] === candidates[i - 1]) continue; // dedup
current.push(candidates[i]);
backtrack(i + 1, current, remaining - candidates[i]); // i+1: no reuse
current.pop();
}
}
backtrack(0, [], target);
return result;
}
Dry run on [1, 1, 2, 5, 6, 7, 10], target = 8 (after sort):
backtrack(0, [], 8)
i=0: push 1 → backtrack(1, [1], 7)
i=1: push 1 → backtrack(2, [1,1], 6)
i=2: push 2 → backtrack(3, [1,1,2], 4)
i=3: push 5 → remaining = -1? No, 5>4 → BREAK
pop 2
i=3: push 5 → backtrack(4, [1,1,5], 1)
i=4: 6>1, BREAK
pop 5
i=4: push 6 → backtrack(5, [1,1,6], 0) → COLLECT [1,1,6] ✓
pop 6
i=5: 7>6, BREAK
pop 1
i=2: push 2 → backtrack(3, [1,2], 5)
i=3: push 5 → backtrack(4, [1,2,5], 0) → COLLECT [1,2,5] ✓
pop 5
i=4: push 6 → remaining = -1? 6>5 → BREAK? No, remaining=5. 6>5 → BREAK
pop 2
i=3: push 5 → backtrack(4, [1,5], 2)
i=4: 6>2, BREAK
pop 5
i=4: push 6 → backtrack(5, [1,6], 1)
i=5: 7>1, BREAK
pop 6
i=5: push 7 → backtrack(6, [1,7], 0) → COLLECT [1,7] ✓
pop 7
pop 1
i=1: i>start (1>0) AND candidates[1]===candidates[0] (1===1) → SKIP
i=2: push 2 → backtrack(3, [2], 6)
i=3: push 5 → remaining=1. 6? No remaining is 6-5=1. Continuing...
i=4: push 6 → backtrack(5, [2,6], 0) → COLLECT [2,6] ✓
pop 6
i=5: 7>6, BREAK? No, remaining=6. push 7 → backtrack(6, [2,7], -1) → skip (>remaining)
Actually: 7>6 → BREAK
pop 2
i=3: push 5 → backtrack(4, [5], 3)
i=4: 6>3, BREAK
pop 5
i=4: push 6 → backtrack(5, [6], 2)
i=5: 7>2, BREAK
pop 6
i=5: push 7 → backtrack(6, [7], 1)
nothing, BREAK
pop 7
i=6: push 10 → 10>8, BREAK
Result: [[1,1,6], [1,2,5], [1,7], [2,6]]. ✓
Comparison table — the three Combination Sum variants:
| Problem | Reuse? | Duplicates in input? | Key code difference |
|---|---|---|---|
| Sum I (LeetCode 39) | Yes | No | backtrack(i, ...) |
| Sum II (LeetCode 40) | No | Yes | backtrack(i+1, ...) + dedup |
| Sum III (LeetCode 216) | No | No, 1-9 | backtrack(i+1, ...), k-size |
Problem 4: Permutations II (with duplicates)
LeetCode 47
Given [1, 1, 2], return all unique permutations.
What do I have? Array with possible duplicates.
What do I want? All unique orderings: [[1,1,2],[1,2,1],[2,1,1]].
Brute force? Generate all permutations, put in a Set (O(n! × n)).
Where is waste? When two elements are equal, swapping them produces the same permutation. Skip the second occurrence at each level of the tree.
The deduplication rule for permutations: skip nums[i] if nums[i] === nums[i-1] AND used[i-1] is false.
Why used[i-1] === false? It means the previous equal element was not chosen earlier in the current path — meaning it's available at the same tree level. If we're at the same level and the previous equal element is available, picking the current one would create the same branch as picking the previous one would. Skip.
function permuteUnique(nums) {
nums.sort((a, b) => a - b);
const result = [];
const used = new Array(nums.length).fill(false);
function backtrack(current) {
if (current.length === nums.length) {
result.push([...current]);
return;
}
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue;
// Dedup: skip if same as prev AND prev not used (same level, not a parent)
if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue;
used[i] = true;
current.push(nums[i]);
backtrack(current);
current.pop();
used[i] = false;
}
}
backtrack([]);
return result;
}
Dry run on [1, 1, 2]:
backtrack([])
i=0: used[0]=false, skip check (i=0). use 1(idx0) → backtrack([1])
i=0: used[0]=true, skip
i=1: used[1]=false. nums[1]===nums[0] (1===1) AND !used[0]? used[0]=true → !true=false
→ condition is false → DON'T skip. use 1(idx1) → backtrack([1,1])
i=0,1: used. i=2: use 2 → backtrack([1,1,2]) → COLLECT [1,1,2]
unuse 1(idx1)
i=2: use 2 → backtrack([1,2])
i=0: use 1(idx0) → backtrack([1,2,1]) → COLLECT [1,2,1]
i=1: nums[1]===nums[0] AND !used[0]? used[0]=false → !false=true → SKIP
unuse 2
unuse 1(idx0)
i=1: nums[1]===nums[0] (1===1) AND !used[0]? used[0]=false → !false=true → SKIP
i=2: use 2 → backtrack([2])
i=0: use 1(idx0) → backtrack([2,1])
i=0: used. i=1: nums[1]===nums[0] AND !used[0]? used[0]=true → false → DON'T skip
use 1(idx1) → backtrack([2,1,1]) → COLLECT [2,1,1]
unuse 1(idx0)
i=1: nums[1]===nums[0] AND !used[0]? used[0]=false → SKIP
unuse 2
Result: [[1,1,2],[1,2,1],[2,1,1]]. ✓ Three unique permutations, not six (= 3! / 2! for two 1s).
Problem 5: Word Search
LeetCode 79
Given a 2D grid and a word, return true if the word exists as a path of adjacent cells (horizontally or vertically adjacent, each cell used at most once).
What do I have? board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED".
What do I want? true if word exists as a valid path.
Brute force? For each starting cell, try all paths of length word.length. O(rows × cols × 4^L).
Where is waste? At each cell, if the character doesn't match the next expected character, stop. If the cell was already visited in this path, stop.
function exist(board, word) {
const rows = board.length;
const cols = board[0].length;
const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
function backtrack(r, c, i) {
if (i === word.length) return true; // matched all characters
if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
if (board[r][c] !== word[i]) return false; // mismatch — prune
if (board[r][c] === '#') return false; // already used
const temp = board[r][c];
board[r][c] = '#'; // CHOOSE: mark as visited
let found = false;
for (const [dr, dc] of dirs) {
if (backtrack(r + dr, c + dc, i + 1)) { found = true; break; }
}
board[r][c] = temp; // UNCHOOSE: restore
return found;
}
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (backtrack(r, c, 0)) return true;
}
}
return false;
}
Full dry run on board above, word = "ABCCED":
Grid (0-indexed, showing [row][col]):
[A][B][C][E]
[S][F][C][S]
[A][D][E][E]
Try start at (0,0): board[0][0]='A' === word[0]='A' ✓
Mark (0,0)='#', explore neighbors for word[1]='B':
down (1,0): board[1][0]='S' ≠ 'B' → fail
up (-1,0): out of bounds → fail
right (0,1): board[0][1]='B' === 'B' ✓
Mark (0,1)='#', explore for word[2]='C':
down (1,1): board[1][1]='F' ≠ 'C' → fail
up (-1,1): out of bounds → fail
right (0,2): board[0][2]='C' === 'C' ✓
Mark (0,2)='#', explore for word[3]='C':
down (1,2): board[1][2]='C' === 'C' ✓
Mark (1,2)='#', explore for word[4]='E':
down (2,2): board[2][2]='E' === 'E' ✓
Mark (2,2)='#', explore for word[5]='D':
down (3,2): out of bounds → fail
up (1,2): '#' → fail
right (2,3): board[2][3]='E' ≠ 'D' → fail
left (2,1): board[2][1]='D' === 'D' ✓
Mark (2,1)='#', i=6 === word.length=6 → return TRUE ✓
Path: (0,0)→(0,1)→(0,2)→(1,2)→(2,2)→(2,1) = A→B→C→C→E→D = "ABCCED". ✓
Why mark with '#' instead of a visited set? Both work. The '#' approach avoids the O(1) Set overhead and the need to pass visited through the call stack. Since we restore the original character on backtrack, the board is never permanently modified.
Time complexity: O(rows × cols × 4^L). The outer loop tries each cell as start. The inner recursion has branching factor 4 and depth L. Character mismatch prunes most branches early.
Problem 6: Palindrome Partitioning
LeetCode 131
Given string "aab", return all ways to partition it into substrings where every substring is a palindrome: [["a","a","b"],["aa","b"]].
What do I have? String s.
What do I want? All partitions where every part is a palindrome.
Decision at each step? For the current starting index, choose where the first partition ends.
When to prune? If s[start..end] is not a palindrome, don't recurse.
function partition(s) {
const result = [];
function isPalin(str, l, r) {
while (l < r) {
if (str[l] !== str[r]) return false;
l++; r--;
}
return true;
}
function backtrack(start, current) {
if (start === s.length) {
result.push([...current]);
return;
}
for (let end = start; end < s.length; end++) {
if (!isPalin(s, start, end)) continue; // prune: not palindrome
current.push(s.slice(start, end + 1));
backtrack(end + 1, current);
current.pop();
}
}
backtrack(0, []);
return result;
}
Full dry run on "aab":
backtrack(0, [])
end=0: s[0..0]="a", isPalin? yes → push "a"
backtrack(1, ["a"])
end=1: s[1..1]="a", isPalin? yes → push "a"
backtrack(2, ["a","a"])
end=2: s[2..2]="b", isPalin? yes → push "b"
backtrack(3, ["a","a","b"]) → start=3=s.length → COLLECT ["a","a","b"] ✓
pop "b"
pop "a"
end=2: s[1..2]="ab", isPalin? a≠b → NO, skip
pop "a" (end=0's push)
end=1: s[0..1]="aa", isPalin? a===a yes → push "aa"
backtrack(2, ["aa"])
end=2: s[2..2]="b", isPalin? yes → push "b"
backtrack(3, ["aa","b"]) → start=3=s.length → COLLECT ["aa","b"] ✓
pop "b"
pop "aa"
end=2: s[0..2]="aab", isPalin? a≠b → NO, skip
Result: [["a","a","b"],["aa","b"]]. ✓
Optimization for interviews: If the string is long, precompute isPalin[i][j] using DP in O(n²) time before backtracking, so each palindrome check is O(1). This makes the overall complexity O(n × 2^n) instead of O(n² × 2^n).
Problem 7: N-Queens (Return Count)
LeetCode 52
Instead of returning all solutions, return just the count.
This is a common follow-up question. Instead of collecting boards, increment a counter.
function totalNQueens(n) {
let count = 0;
const cols = new Set();
const diag1 = new Set(); // row - col
const diag2 = new Set(); // row + col
function backtrack(row) {
if (row === n) { count++; return; }
for (let col = 0; col < n; col++) {
if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) continue;
cols.add(col); diag1.add(row - col); diag2.add(row + col);
backtrack(row + 1);
cols.delete(col); diag1.delete(row - col); diag2.delete(row + col);
}
}
backtrack(0);
return count;
}
Same structure, no board needed. For n=8, returns 92.
What the interviewer is testing: Can you extract just the count without changing the overall structure? The answer is: yes — just change result.push(...) to count++ and remove board construction. The backtracking logic is identical.
Problem 8: Letter Combinations of a Phone Number
LeetCode 17
Given digits "23", return all letter combinations: ["ad","ae","af","bd","be","bf","cd","ce","cf"].
2 → "abc"
3 → "def"
4 → "ghi"
5 → "jkl"
6 → "mno"
7 → "pqrs"
8 → "tuv"
9 → "wxyz"
What do I have? String of digits.
Decision at each step? For digit at position i, choose one of its letters.
Base case? When i === digits.length, collect current string.
function letterCombinations(digits) {
if (!digits.length) return [];
const map = {
'2': 'abc', '3': 'def', '4': 'ghi',
'5': 'jkl', '6': 'mno', '7': 'pqrs',
'8': 'tuv', '9': 'wxyz'
};
const result = [];
function backtrack(i, current) {
if (i === digits.length) {
result.push(current.join(''));
return;
}
for (const ch of map[digits[i]]) {
current.push(ch);
backtrack(i + 1, current);
current.pop();
}
}
backtrack(0, []);
return result;
}
Dry run on "23":
backtrack(0, [])
ch='a': push 'a'
backtrack(1, ['a'])
ch='d': push → backtrack(2, ['a','d']) → collect "ad"
pop 'd'
ch='e': push → collect "ae"
pop 'e'
ch='f': push → collect "af"
pop 'f'
pop 'a'
ch='b': push 'b' → [bd, be, bf]
ch='c': push 'c' → [cd, ce, cf]
Result: ["ad","ae","af","bd","be","bf","cd","ce","cf"]. ✓
Time complexity: O(4^n × n) where n is the number of digits and 4 is the max letters per digit (7 and 9 have 4). For n=4 (typical phone number substring), this is 256 combinations — completely fine.
Pattern Recognition Summary
Before you code, answer: what shape is the decision tree?
Subsets shape: "Find all subsets / power set." One decision per element: include or skip. Use for i from start to end and always collect at each node.
Combination shape: "Find all combinations that satisfy a constraint." One decision per step: which element to add next. Use for i from start and collect only at leaves (when constraint is met). Two variants: reuse (backtrack(i, ...)) or no reuse (backtrack(i+1, ...)).
Permutation shape: "Find all orderings." At each step, pick any unused element. Use used[] array. Always goes to depth n.
Grid DFS shape: "Find a path / word in a grid." Decisions are which of 4 (or 8) neighbors to visit. Mark visited with '#' or a set.
The dedup rule (applies to subsets + combinations with duplicate inputs):
if (i > start && nums[i] === nums[i - 1]) continue;
The permutation dedup rule (duplicate inputs):
if (i > 0 && nums[i] === nums[i-1] && !used[i-1]) continue;
Interview Tip: What Interviewers Ask After the First Solution
-
"What's the time complexity?" — Name the shape. Subsets = O(2^n). Permutations = O(n!). Combinations = somewhere between.
-
"Can you optimize?" — For palindrome partitioning: precompute
isPalin[i][j]. For N-Queens: bit manipulation instead of Sets. -
"What if input has duplicates?" — Add sort + skip check. Know both dedup rules (one for combinations, one for permutations).
-
"How would you count solutions instead of listing them?" — Change
result.push(...)tocount++. The algorithm structure is identical. -
"Can DP solve this?" — If the problem asks for count, usually yes. If it asks for enumerate all, backtracking is the right tool and DP won't work directly.
Complexity Quick Reference
| Problem | Time | Space (excluding output) |
|---|---|---|
| Subsets II | O(2^n × n) | O(n) call stack |
| Combination Sum I | O(n^(T/m) × T/m) | O(T/m) call stack |
| Combination Sum II | O(2^n × n) | O(n) |
| Permutations II | O(n! × n) | O(n) |
| Word Search | O(rows × cols × 4^L) | O(L) |
| Palindrome Partitioning | O(2^n × n) | O(n) |
| N-Queens | O(n!) pruned heavily | O(n) |
| Letter Combinations | O(4^n × n) | O(n) |
Space is O(n) for the call stack depth (not counting the output array). The output itself can be exponentially large.