The choose → explore → undo templateCore idea
Choose
Pick the next candidate and add it to the partial solution.
Explore
Recurse with the new partial solution.
Undo
Remove the choice, so the next branch starts clean.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","actorBkg":"#e7f5ff","actorBorder":"#1e1e1e","noteBkgColor":"#fff9db","noteBorderColor":"#1e1e1e"}}}%%
graph TD
R["[ ]"] -->|take 1| A["[1]"]
R -->|skip 1| B["[ ]"]
A -->|take 2| A1["[1, 2]"]
A -->|skip 2| A2["[1]"]
B -->|take 2| B1["[2]"]
B -->|skip 2| B2["[ ]"]
class R yellow
class A,B blue
class A1,A2,B1,B2 green
classDef orange fill:#ffd8a8,stroke:#1e1e1e,color:#1e1e1e
classDef blue fill:#a5d8ff,stroke:#1e1e1e,color:#1e1e1e
classDef green fill:#b2f2bb,stroke:#1e1e1e,color:#1e1e1e
classDef red fill:#ffc9c9,stroke:#1e1e1e,color:#1e1e1e
classDef violet fill:#d0bfff,stroke:#1e1e1e,color:#1e1e1e
classDef yellow fill:#ffec99,stroke:#1e1e1e,color:#1e1e1e
classDef grey fill:#e9ecef,stroke:#1e1e1e,color:#1e1e1eSubsetsPattern
Every element is either in or out, so every node you reach is a valid subset. Copy the current path before saving it.
function subsets(nums: number[]): number[][] {
const res: number[][] = [];
const path: number[] = [];
const dfs = (start: number) => {
res.push([...path]);
for (let i = start; i < nums.length; i++) {
path.push(nums[i]); // choose
dfs(i + 1); // explore
path.pop(); // undo
}
};
dfs(0);
return res;
}PermutationsPattern
Unlike subsets, order matters and every element is used exactly once. Track which indices are already taken.
function permute(nums: number[]): number[][] {
const res: number[][] = [];
const path: number[] = [];
const used = new Array(nums.length).fill(false);
const dfs = () => {
if (path.length === nums.length) { res.push([...path]); return; }
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true; // choose
path.push(nums[i]);
dfs(); // explore
path.pop();
used[i] = false; // undo
}
};
dfs();
return res;
}Combinations and the start-index rulePattern
Combinations are subsets of a fixed size k. Passing start means you only pick numbers after the last one you picked, so [1,2] and [2,1] are not both generated. That one parameter turns a permutation solver into a combination solver.
function combine(n: number, k: number): number[][] {
const res: number[][] = [];
const path: number[] = [];
const dfs = (start: number) => {
if (path.length === k) { res.push([...path]); return; }
for (let i = start; i <= n; i++) {
path.push(i);
dfs(i + 1);
path.pop();
}
};
dfs(1);
return res;
}| Problem | Order matters? | What controls the loop |
|---|---|---|
| Subsets | No | start index; save at every node |
| Combinations | No | start index; save when size = k |
| Permutations | Yes | used[] array; save when all are used |
N-Queens: constant-time checksPattern
Place one queen per row. Keep sets of used columns, diagonals (row − col) and anti-diagonals (row + col), so checking whether a square is attacked takes O(1).
function solveNQueens(n: number): string[][] {
const res: string[][] = [];
const cols = new Set<number>();
const diag = new Set<number>(); // row - col
const anti = new Set<number>(); // row + col
const board: string[][] = Array.from({ length: n }, () => '.'.repeat(n).split(''));
const dfs = (row: number) => {
if (row === n) { res.push(board.map(r => r.join(''))); return; }
for (let col = 0; col < n; col++) {
if (cols.has(col) || diag.has(row - col) || anti.has(row + col)) continue;
board[row][col] = 'Q';
cols.add(col); diag.add(row - col); anti.add(row + col);
dfs(row + 1);
board[row][col] = '.';
cols.delete(col); diag.delete(row - col); anti.delete(row + col);
}
};
dfs(0);
return res;
}Pruning: when to cut a branchHow it works
Pruning means stopping a path early because it can never lead to an answer. It is what keeps exponential searches fast enough.
Skip duplicates
Sort the input, then skip an element equal to the one before it at the same level.
Target already missed
In combination sum with positive numbers, stop once target < nums[i].
Check before recursing
As in N-Queens, reject a bad placement right away instead of after the recursive call.
Not enough left
Stop when path.length + remaining < k: you can never reach size k.
Common mistakesPitfalls
In the interviewIn the interview
Frequently asked questionsFAQ
How do you optimize a backtracking solution?
Prune as early as possible, deduplicate choices at the same level, and use start-index or used-flag tricks to shrink the search space. For heavily constrained problems like N-Queens, keeping sets of occupied columns and diagonals makes each validity check O(1), so worst-case exponential growth stops turning into a timeout.
Is backtracking the same as DFS?
Backtracking is a depth-first search over the space of partial solutions, with an explicit undo step. DFS on a tree or grid is the traversal; backtracking adds pruning of invalid partial states and the push/pop bookkeeping that recursion alone does not provide.
When should you avoid backtracking?
Avoid it when the problem wants a single optimal path rather than an enumeration of many candidates, or when the same subproblem recurs. Both cases are better served by dynamic programming, since memoization collapses the overlapping states that plain backtracking would recompute again and again on the same input.
Now explain backtracking to me out loud
I'll give you interview problems and ask follow-ups, like a real interviewer.