Try every valid path — if it fails, undo and try the next one. Build answers piece by piece, prune bad branches early.
You explore all possibilities by making a choice, going deeper, and undoing it when it leads nowhere — then trying the next option.
Real-world analogy: You're solving a Sudoku. You write a number in a cell, check if it violates any rule — if it does, you erase it and try the next digit. That erase step is backtracking.
Another analogy: GPS gives you a wrong turn. You don't restart from home — you go back to the last junction and take a different road.
Generate ALL arrangements → filter valid ones → slow and wasteful
Prune a branch the moment it's invalid → explore only promising paths
Pick one option from available choices (a number, character, element, direction)
Recurse with that choice applied. Go deeper into the tree.
After recursion returns, undo the choice. Restore state for next iteration.
start index — loop from i = start, recurse with i+1 (or i for repetition)
boolean used[] — loop always from i = 0, skip used[i]
if (!isValid()) continue inside loop — place, recurse row+1, unplace
grid[r][c]='#', explore 4 dirs, then restore original char
end from start to n, check substring validity, recurse with end+1
| Question to Ask | Subset Type | Permutation Type |
|---|---|---|
| Does [1,2] == [2,1] ? | ✅ Yes, same | ❌ No, different |
| Loop starts at | i = start (forward only) | i = 0 (always full scan) |
| State variable | int start | boolean[] used |
| Recurse with | i + 1 (or i for reuse) | same used[] passed down |
| Result added when | Every node (subsets) / leaf (combos) | Only at leaf (path.size == n) |
| Example problem | LC 78 Subsets, LC 39 Comb Sum | LC 46 Permutations |
Goal reached? Save result and return. (path complete, sum == target, row == n)
Invalid state? Return immediately. (out of bounds, constraint violated, sum exceeded)
For each available option at this level...
Apply the choice (add to path, mark used), then recurse.
After recursion returns, undo the choice. This is the backtrack step. Never skip it.
// ── UNIVERSAL BACKTRACKING TEMPLATE ────────────────────────── void backtrack(List<Integer> path, int start /* or other state */) { // ① BASE CASE ── goal reached? if (goalReached()) { result.add(new ArrayList<>(path)); // ← copy, not reference! return; } // ② PRUNE ── invalid state? if (isInvalid()) return; // ③ LOOP OVER CHOICES for (int i = start; i < choices.length; i++) { // ④ CHOOSE + EXPLORE path.add(choices[i]); // make the move backtrack(path, i + 1); // go deeper // ⑤ UNCHOOSE ← the backtrack step path.remove(path.size() - 1); // undo the move } }
# ── UNIVERSAL BACKTRACKING TEMPLATE ────────────────────────── def backtrack(path, start): # ① BASE CASE if goal_reached(): result.append(path[:]) # shallow copy return # ② PRUNE if is_invalid(): return # ③ LOOP for i in range(start, len(choices)): # ④ CHOOSE + EXPLORE path.append(choices[i]) backtrack(path, i + 1) # ⑤ UNCHOOSE ← the backtrack step path.pop()
// ── UNIVERSAL BACKTRACKING TEMPLATE ────────────────────────── void backtrack(vector<int>& path, int start) { // ① BASE CASE if (goalReached()) { result.push_back(path); return; } // ② PRUNE if (isInvalid()) return; // ③ LOOP for (int i = start; i < choices.size(); i++) { // ④ CHOOSE + EXPLORE path.push_back(choices[i]); backtrack(path, i + 1); // ⑤ UNCHOOSE path.pop_back(); } }
result.add(path) adds a reference. When path changes, the stored list changes too. Always use new ArrayList<>(path).Each node = a subset. At each level, you decide: include next element or skip to next. Start index moves forward so you never re-pick.
Every level = one position in the output. At each node, loop from 0 (not start), skip already-used elements via used[].
Candidates=[2,3,6,7], target=7. Same element CAN be reused (recurse with same i, not i+1). Prune when sum exceeds target.
Word="CAT". Starting at (0,0)='C'. Each node = one cell. 4 children = Up/Down/Left/Right. Mark '#' to avoid re-visiting same cell.
Signal: "All subsets / combinations" — order doesn't matter — use start index.
List<List<Integer>> result = new ArrayList<>(); public List<List<Integer>> subsets(int[] nums) { backtrack(nums, 0, new ArrayList<>()); return result; } void backtrack(int[] nums, int start, List<Integer> path) { result.add(new ArrayList<>(path)); // ① add at EVERY node for (int i = start; i < nums.length; i++) { // ③ start from 'start' path.add(nums[i]); // ④ choose backtrack(nums, i + 1, path); // ④ explore (i+1 = no repeat) path.remove(path.size() - 1); // ⑤ unchoose } } // Signal: "start" param + loop from start → SUBSET type
// LC 39 — Combination Sum (element CAN be reused) void backtrack(int[] cands, int start, int remain, List<Integer> path) { if (remain == 0) { // ① base case: exact sum result.add(new ArrayList<>(path)); return; } if (remain < 0) return; // ② prune: exceeded target for (int i = start; i < cands.length; i++) { if (cands[i] > remain) break; // sorted → no point continuing path.add(cands[i]); backtrack(cands, i, remain - cands[i], path); // i not i+1 (reuse ok) path.remove(path.size() - 1); } } // Note: recurse with 'i' (not i+1) = same element can be reused // Note: recurse with 'i+1' = each element used at most once (LC 40)
Signal: "All arrangements / orderings" — order matters — use visited[] array, loop always from 0.
boolean[] used; void backtrack(int[] nums, List<Integer> path) { if (path.size() == nums.length) { // ① base: all elements placed result.add(new ArrayList<>(path)); return; } for (int i = 0; i < nums.length; i++) { // ③ always loop from 0! if (used[i]) continue; // skip already in path used[i] = true; // ④ choose path.add(nums[i]); backtrack(nums, path); // ④ explore used[i] = false; // ⑤ unchoose path.remove(path.size() - 1); } } // Signal: loop from 0 + used[] array → PERMUTATION type
// LC 47 — Permutations II (with duplicates) // Extra: sort first + skip condition Arrays.sort(nums); // sort first! boolean[] used = new boolean[nums.length]; void backtrack(int[] nums, List<Integer> path) { if (path.size() == nums.length) { result.add(new ArrayList<>(path)); return; } for (int i = 0; i < nums.length; i++) { if (used[i]) continue; // Skip duplicate: same value, previous sibling already explored if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue; used[i] = true; path.add(nums[i]); backtrack(nums, path); used[i] = false; path.remove(path.size() - 1); } } // !used[i-1] means: same value's "first" use hasn't finished yet → skip
Signal: Hard placement rules — must call isValid() before every placement. Place → recurse row+1 → unplace.
void solve(char[][] board, int row) { if (row == board.length) { // ① base: all rows filled result.add(build(board)); return; } for (int col = 0; col < board.length; col++) { if (!isValid(board, row, col)) continue; // ② prune invalid board[row][col] = 'Q'; // ④ choose: place queen solve(board, row + 1); // ④ explore next row board[row][col] = '.'; // ⑤ unchoose: remove queen } } boolean isValid(char[][] board, int row, int col) { // Check column (no queen in same column above) for (int r = 0; r < row; r++) if (board[r][col] == 'Q') return false; // Check diagonals for (int r = row-1, c = col-1; r>=0&&c>=0; r--,c--) if (board[r][c] == 'Q') return false; for (int r = row-1, c = col+1; r>=0&&c<board.length; r--,c++) if (board[r][c] == 'Q') return false; return true; } // Signal: isValid() before placement + go row by row → CONSTRAINT type
Signal: 2D grid, DFS in 4 directions, mark visited using '#' overwrite trick.
boolean exist(char[][] board, String word) { for (int r = 0; r < board.length; r++) for (int c = 0; c < board[0].length; c++) if (dfs(board, word, r, c, 0)) return true; return false; } boolean dfs(char[][] board, String word, int r, int c, int idx) { if (idx == word.length()) return true; // base: full word matched if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] != word.charAt(idx)) return false; // prune char tmp = board[r][c]; board[r][c] = '#'; // choose: mark visited in-place boolean found = dfs(board, word, r+1, c, idx+1) || dfs(board, word, r-1, c, idx+1) || dfs(board, word, r, c+1, idx+1) || dfs(board, word, r, c-1, idx+1); board[r][c] = tmp; // unchoose: restore cell return found; } // Signal: r/c params + 4 direction recursion + '#' overwrite → GRID type
Signal: "Partition into valid segments" — loop end index, validate each substring, recurse from end+1.
void backtrack(String s, int start, List<String> path) { if (start == s.length()) { // base: consumed whole string result.add(new ArrayList<>(path)); return; } for (int end = start; end < s.length(); end++) { String sub = s.substring(start, end + 1); if (!isPalindrome(sub)) continue; // prune: invalid segment path.add(sub); // choose backtrack(s, end + 1, path); // explore from next char path.remove(path.size() - 1); // unchoose } } // Signal: loop 'end' from start, validate substring → PARTITION type // Same pattern for LC 93 (valid IP) — just validate IP segment instead
Does order matter?
YES → Permutation (used[])
NO → Subset (start index)
Is it a 2D grid?
YES → Grid (r,c + 4 dirs)
NO → Not grid
Hard placement rules?
YES → Constraint (isValid())
String splits? → Partition
// Subset with duplicates (LC 40, LC 90) Arrays.sort(nums); for (int i = start; i < nums.length; i++) { if (i > start && nums[i] == nums[i-1]) continue; // skip same-level dup // ... backtrack body } // i > start = same value already tried at this level → skip // Permutation with duplicates (LC 47) if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue; // !used[i-1] = previous same-value already explored and backtracked → skip
| Type | Time | Space | Why |
|---|---|---|---|
| 🟢 Subsets | O(2ⁿ × n) | O(n) | 2 choices per element, n to copy |
| 🟣 Permutations | O(n! × n) | O(n) | n! leaves, copy each takes O(n) |
| 🟠 Combination Sum | O(2^t) | O(t) | t = target value |
| 🟠 N-Queens | O(n!) | O(n²) | Board storage per state |
| 🟦 Word Search | O(m×n×4^L) | O(L) | 4 dirs from every cell, L=word len |
| 🩵 Palindrome Part. | O(n × 2ⁿ) | O(n) | 2ⁿ⁻¹ ways to partition |
i (not i+1). Base case: remain == 0.if (used[i]) continue; — What type is this?used[i] + loop always from i=0 = Permutation type. This is the single clearest code signal. Subset type uses an int start parameter and loops from start, never from 0.result.add(path); inside their backtrack function. What is wrong?path is an object reference. After unchoose modifies it, the "saved" result also changes — they're the same object. Fix: result.add(new ArrayList<>(path)) to create an independent copy.break instead of continue when candidates[i] > remain?candidates[i] > remain, then candidates[i+1] and beyond are also too large. break exits the loop entirely (better pruning). continue would wastefully check the next element which is also invalid.board[r][c] = '#' and the DFS returns, you MUST restore the cell. Why?board[r][c] = tmp restores the cell for all other branches.