Algorithms
Backtracking Explore & Undo
Choose → explore → unchoose. Backtracking is DFS on the decision tree — it systematically tries every valid option, undoes the choice, and tries the next. One template handles subsets, permutations, combinations, N-Queens, Sudoku, and every "generate all valid X" problem.
Foundations · Array · HashMap · DFS · Sorting · Binary Search · Two Pointers · Sliding Window · Dynamic Prog. · Backtracking · Greedy
01
Section One · Foundation
What is Backtracking?
Backtracking is a systematic way to explore all possible configurations by building candidates incrementally and abandoning ("pruning") a candidate as soon as it's clear it can't lead to a valid solution. It's DFS on a decision tree: at each node, you make a choice, recurse to explore the consequences, then undo the choice and try the next option. The three steps — choose, explore, unchoose — form a universal template that handles subsets (include or skip each element), permutations (place each unused element), combinations (pick k from n), and constraint satisfaction (N-Queens, Sudoku, word search). Backtracking is inherently exponential — for n elements, subsets = O(2ⁿ), permutations = O(n!), combinations = O(C(n,k)) — but pruning invalid branches early makes it practical. In interviews, the template is always the same; the only thing that changes is the decision at each node and the pruning condition.
Analogy: Navigating a maze. At each fork, you pick a direction (choose), walk until you hit a dead end or find the exit (explore), then walk back to the fork and try the other direction (unchoose). You never revisit a path you've already fully explored. Pruning is when you can see the dead end ahead and skip the path without walking all the way.
02
Section Two · Mental Model
How It Thinks
"Generate all valid X" — the problem asks for all configurations, not just one optimal answer
▶
Backtracking: DFS the decision tree, collect every valid leaf (or intermediate) node. Unlike DP which optimises, backtracking enumerates.
Choose → Explore → Unchoose: add to current path, recurse, remove from current path
▶
The path is reused across all branches — it's mutable state. The "unchoose" step restores it to the state before the choice, enabling the next branch to start clean.
The
start parameter controls which elements are available▶
For subsets/combinations:
start = i + 1 → never revisit earlier elements → no duplicates. For permutations: start = 0 + used[] → any unused element can be placed.Pruning: skip branches that can't lead to valid solutions
▶
Dramatically reduces the search space. E.g., in N-Queens: skip columns/diagonals already attacked. In combination sum: skip if remaining sum is negative. Sorting the input enables early termination.
Duplicate elements in input → duplicate results
▶
Sort first. Then skip:
if (i > start && nums[i] == nums[i-1]) continue; — prevents choosing the same value at the same tree level. This works for subsets II, combinations II, permutations II.Copy the path when adding to result — don't add the reference
▶
result.add(new ArrayList<>(path)) — the path is mutable and will be modified by unchoose. Without copying, all entries in result point to the same (eventually empty) list.03
Section Three · Template
The Universal Backtracking Template
Pseudocode
function backtrack(result, path, choices, start):
if isGoal(path): // base case — reached a valid solution
result.add(copy(path)) // COPY, not reference return for i = start to choices.length - 1:
if shouldPrune(i): continue // prune invalid branches
path.add(choices[i]) // ① CHOOSE backtrack(result, path, choices,
nextStart(i)) // ② EXPLORE
path.removeLast() // ③ UNCHOOSE
| Problem | isGoal() | nextStart | Prune |
|---|---|---|---|
| Subsets | Always (collect at every node) | i + 1 | — |
| Combinations (k) | path.size() == k | i + 1 | remaining < k - path.size() |
| Permutations | path.size() == n | 0 + used[] | used[i] |
| Combination Sum | remaining == 0 | i (reuse) or i + 1 (no reuse) | remaining < 0 |
| N-Queens | row == n | next row, col 0..n-1 | column/diagonal attacked |
Every backtracking problem is the same template.:
- The only things that change: (1) what you add to the path, (2) when the path is "complete," (3) what the next valid choices are, and (4) when to prune.
- Master the template once, and every problem is a fill-in-the-blanks exercise.
04
Section Four · Subsets
Subsets (Power Set)
Subsets (LC 78)
Given a set of distinct integers, return all possible subsets.
Java
List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(result, new ArrayList<>(), nums, 0);
return result;
}
void backtrack(List<List<Integer>> res, List<Integer> path,
int[] nums, int start) {
res.add(new ArrayList<>(path)); // collect at EVERY node for (int i = start; i < nums.length; i++) {
path.add(nums[i]); // choose backtrack(res, path, nums, i + 1); // explore (i+1 → no reuse)
path.removeLast(); // unchoose
}
}
Subsets II — With Duplicates (LC 90)
Input may have duplicates. Return all unique subsets.
Key change: sort + skip duplicates at same level
Arrays.sort(nums); // sort first! // Inside the loop, add this skip: if (i > start && nums[i] == nums[i - 1]) continue;
// "i > start" means: skip only at the SAME level, not deeper
Subsets = collect at every node. Unlike combinations (collect at leaves of depth k) or permutations (collect at leaves of depth n), subsets add the current path to the result at the BEGINNING of every recursion call — before the loop.
05
Section Five · Permutations
Permutations
Permutations (LC 46)
Given distinct integers, return all possible permutations.
Java
List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(result, new ArrayList<>(), nums, new boolean[nums.length]);
return result;
}
void backtrack(List<List<Integer>> res, List<Integer> path,
int[] nums, boolean[] used) {
if (path.size() == nums.length) { // all placed → complete perm
res.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) { // start from 0 every time if (used[i]) continue; // skip already-used
used[i] = true; // choose
path.add(nums[i]);
backtrack(res, path, nums, used); // explore
path.removeLast(); // unchoose
used[i] = false;
}
}
Subsets / Combinations
start = i + 1
Never revisit earlier elements. Order doesn't matter: 2 and 1 are the same subset. Loop from start forward.
Permutations
start = 0 + used[]
Any unused element can be placed next. Order matters: [1,2] and [2,1] are different permutations. Loop from 0, skip used.
06
Section Six · Combinations
Combinations & Combination Sum
Combinations (LC 77)
Return all combinations of k numbers from 1..n.
Java
void backtrack(List<List<Integer>> res, List<Integer> path,
int n, int k, int start) {
if (path.size() == k) { // reached target size
res.add(new ArrayList<>(path));
return;
}
for (int i = start; i <= n - (k - path.size()) + 1; i++) { // prune!
path.add(i);
backtrack(res, path, n, k, i + 1);
path.removeLast();
}
}
Combination Sum (LC 39)
Find all unique combinations that sum to target. Candidates may be reused.
Java — key difference: recurse with
i (not i+1) for reuse void backtrack(List<List<Integer>> res, List<Integer> path,
int[] cands, int remain, int start) {
if (remain == 0) {
res.add(new ArrayList<>(path));
return;
}
for (int i = start; i < cands.length; i++) {
if (cands[i] > remain) break; // prune (array sorted)
path.add(cands[i]);
backtrack(res, path, cands, remain - cands[i], i); // i, not i+1!
path.removeLast();
}
}
Common Mistake: Combination Sum allows reuse (
i), Combination Sum II does NOT (i+1) and needs dedup (if (i > start && cands[i] == cands[i-1]) continue). Mixing up i vs i+1 is the #1 backtracking bug.
07
Section Seven · Constraint Problems
N-Queens & Sudoku
Constraint-satisfaction problems use the same backtracking template but with more complex pruning. Instead of "choose an element from a list," you "place a queen in a row" or "fill a cell with a digit" — and the pruning checks are domain-specific constraints.
N-Queens (LC 51)
Place n queens on an n×n chessboard so no two attack each other.
Approach
// Place one queen per row. For each row, try each column. // Prune: skip if column, diagonal, or anti-diagonal is attacked. // Track with 3 sets: cols, diags (row-col), antiDiags (row+col). void solve(int row, int n, List<String> board,
Set cols, Set diags, Set antiDiags) {
if (row == n) { result.add(new ArrayList<>(board)); return; }
for (int col = 0; col < n; col++) {
if (cols.contains(col) || diags.contains(row-col)
|| antiDiags.contains(row+col)) continue; // prune // choose
cols.add(col); diags.add(row-col); antiDiags.add(row+col);
board.set(row, placeQueen(col, n));
solve(row + 1, ...); // explore // unchoose
cols.remove(col); diags.remove(row-col); antiDiags.remove(row+col);
board.set(row, emptyRow(n));
}
}
N-Queens pruning trick:
- Two queens are on the same diagonal if
row1 - col1 == row2 - col2. - Same anti-diagonal if
row1 + col1 == row2 + col2. Track these in two HashSets — O(1) conflict check.
08
Section Eight · Implementation
Build It Once
Build subsets, permutations, and combination sum — the three core variants. Every other backtracking problem is one of these with modified pruning.
Backtracking — Full Implementation
Java — All backtracking patterns
import java.util.*;
public class Backtracking {
// ═══ 1. Subsets ═════════════════════════ O(n × 2ⁿ) static List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
subsetsHelper(res, new ArrayList<>(), nums, 0);
return res;
}
static void subsetsHelper(List<List<Integer>> res,
List<Integer> path, int[] nums, int start) {
res.add(new ArrayList<>(path));
for (int i = start; i < nums.length; i++) {
path.add(nums[i]);
subsetsHelper(res, path, nums, i + 1);
path.removeLast();
}
}
// ═══ 2. Subsets II (with duplicates) ════ O(n × 2ⁿ) static List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
subsets2Helper(res, new ArrayList<>(), nums, 0);
return res;
}
static void subsets2Helper(List<List<Integer>> res,
List<Integer> path, int[] nums, int start) {
res.add(new ArrayList<>(path));
for (int i = start; i < nums.length; i++) {
if (i > start && nums[i] == nums[i-1]) continue;
path.add(nums[i]);
subsets2Helper(res, path, nums, i + 1);
path.removeLast();
}
}
// ═══ 3. Permutations ════════════════════ O(n × n!) static List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
permuteHelper(res, new ArrayList<>(), nums,
new boolean[nums.length]);
return res;
}
static void permuteHelper(List<List<Integer>> res,
List<Integer> path, int[] nums, boolean[] used) {
if (path.size() == nums.length) {
res.add(new ArrayList<>(path)); return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true; path.add(nums[i]);
permuteHelper(res, path, nums, used);
path.removeLast(); used[i] = false;
}
}
// ═══ 4. Combination Sum ═════════════════ O(n^(T/M)) static List<List<Integer>> combinationSum(int[] cands, int target) {
Arrays.sort(cands);
List<List<Integer>> res = new ArrayList<>();
combSumHelper(res, new ArrayList<>(), cands, target, 0);
return res;
}
static void combSumHelper(List<List<Integer>> res,
List<Integer> path, int[] cands, int remain, int start) {
if (remain == 0) {
res.add(new ArrayList<>(path)); return;
}
for (int i = start; i < cands.length; i++) {
if (cands[i] > remain) break;
path.add(cands[i]);
combSumHelper(res, path, cands, remain - cands[i], i);
path.removeLast();
}
}
// ═══ 5. N-Queens ════════════════════════ O(n!) static List<List<String>> solveNQueens(int n) {
List<List<String>> res = new ArrayList<>();
char[][] board = new char[n][n];
for (char[] row : board) Arrays.fill(row, '.');
nqHelper(res, board, 0, new HashSet<>(),
new HashSet<>(), new HashSet<>());
return res;
}
static void nqHelper(List<List<String>> res, char[][] board,
int row, Set<Integer> cols,
Set<Integer> diags, Set<Integer> anti) {
if (row == board.length) {
List<String> snapshot = new ArrayList<>();
for (char[] r : board) snapshot.add(new String(r));
res.add(snapshot); return;
}
for (int c = 0; c < board.length; c++) {
if (cols.contains(c) || diags.contains(row-c)
|| anti.contains(row+c)) continue;
board[row][c] = 'Q';
cols.add(c); diags.add(row-c); anti.add(row+c);
nqHelper(res, board, row+1, cols, diags, anti);
board[row][c] = '.';
cols.remove(c); diags.remove(row-c); anti.remove(row+c);
}
}
public static void main(String[] args) {
System.out.println(subsets(new int[]{1,2,3}));
System.out.println(permute(new int[]{1,2,3}));
System.out.println(combinationSum(new int[]{2,3,6,7}, 7));
System.out.println(solveNQueens(4).size()); // 2
}
}
Python — Backtracking patterns
# ═══ 1. Subsets ═════════════════════════ O(n × 2ⁿ) def subsets(nums):
res = []
def bt(start, path):
res.append(path[:])
for i in range(start, len(nums)):
path.append(nums[i])
bt(i + 1, path)
path.pop()
bt(0, [])
return res
# ═══ 2. Subsets II ══════════════════════ O(n × 2ⁿ) def subsets_with_dup(nums):
nums.sort()
res = []
def bt(start, path):
res.append(path[:])
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i-1]: continue
path.append(nums[i])
bt(i + 1, path)
path.pop()
bt(0, [])
return res
# ═══ 3. Permutations ════════════════════ O(n × n!) def permute(nums):
res = []
used = [False] * len(nums)
def bt(path):
if len(path) == len(nums):
res.append(path[:])
return for i in range(len(nums)):
if used[i]: continue
used[i] = True; path.append(nums[i])
bt(path)
path.pop(); used[i] = False bt([])
return res
# ═══ 4. Combination Sum ═════════════════ O(n^(T/M)) def combination_sum(cands, target):
cands.sort()
res = []
def bt(start, path, remain):
if remain == 0:
res.append(path[:])
return for i in range(start, len(cands)):
if cands[i] > remain: break
path.append(cands[i])
bt(i, path, remain - cands[i]) # i, not i+1
path.pop()
bt(0, [], target)
return res
# ═══ 5. N-Queens ════════════════════════ O(n!) def solve_n_queens(n):
res, cols, diags, anti = [], set(), set(), set()
board = [['.']*n for _ in range(n)]
def bt(row):
if row == n:
res.append([''.join(r) for r in board])
return for c in range(n):
if c in cols or row-c in diags or row+c in anti:
continue
board[row][c] = 'Q'
cols.add(c); diags.add(row-c); anti.add(row+c)
bt(row + 1)
board[row][c] = '.'
cols.remove(c); diags.remove(row-c); anti.remove(row+c)
bt(0)
return res
# Demo
print(subsets([1,2,3]))
print(permute([1,2,3]))
print(combination_sum([2,3,6,7], 7))
print(len(solve_n_queens(4))) # 2
09
Section Nine · Java Reference
Use It In Java
IN JAVA — Backtracking Idioms
Result type
List<List<Integer>> result = new ArrayList<>(); Path (mutable)
List<Integer> path = new ArrayList<>(); Copy to result
result.add(new ArrayList<>(path)); — always copy! | Idiom | Code | When |
|---|---|---|
| Add to path | path.add(x) | Choose |
| Remove from path | path.removeLast() or path.remove(path.size()-1) | Unchoose |
| Skip duplicates | if (i > start && nums[i] == nums[i-1]) continue; | After sorting — same level dedup |
| Used array | boolean[] used = new boolean[n]; | Permutations |
| Early termination | if (cands[i] > remain) break; | Sorted input + target constraint |
| N-Queens sets | Set<Integer> cols, diags, antiDiags | O(1) conflict check |
⚠ Gotcha:
result.add(path) adds a REFERENCE — as you modify path in later recursive calls, the stored list changes too. You'll end up with all entries pointing to the same empty list. Always copy: result.add(new ArrayList<>(path)).
⚠ Gotcha: For Combination Sum (
i = reuse allowed) vs Combination Sum II (i + 1 = no reuse + dedup), mixing up the recursion parameter is the #1 bug. Write a comment next to the recursive call: // i = reuse or // i+1 = no reuse.
10
Section Ten · Practice
Problems To Solve
Backtracking problems cluster into three families: subsets (power set, include/exclude), permutations (arrangments, used[] array), and constraint satisfaction (N-Queens, Sudoku). Master one problem from each family and every other problem is a variant with different pruning.
| Difficulty | Pattern | Problem | Key Insight |
|---|---|---|---|
| Medium | subsets | Subsets — LC 78 | Collect at every node. start = i + 1. No pruning needed. 2ⁿ subsets. |
| Medium | subsets | Subsets II — LC 90 | Sort + if (i > start && nums[i] == nums[i-1]) continue. Same-level dedup. |
| Medium | permutations | Permutations — LC 46 | used[] array. Start from 0 every time. Collect at depth n. |
| Medium | combinations | Combination Sum — LC 39 | Reuse allowed (i). Sort + break when candidate exceeds remainder. |
| Medium | combinations | Combination Sum II — LC 40 | No reuse (i + 1). Sort + skip duplicates at same level. |
| Hard | constraint | N-Queens — LC 51 | Place row by row. Prune via cols/diags/antiDiags sets. O(n!) with pruning. |
Interview Pattern:
- "Generate all valid X" → backtracking.
- The template: define the choice (what goes into the path), the goal (when the path is complete), and the pruning (what to skip).
- Code is always:
path.add(x); recurse(); path.removeLast();. - The hard part is pruning correctly — sorting the input enables most pruning via
breakorcontinue.
→ See all Backtracking problems with full solutions
→ See Interview Patterns for the complete cheat sheet