Notes › DSA
Backtracking
Backtracking builds a solution one choice at a time. After exploring a choice, it undoes it and tries the next one. It is recursion that explores a decision tree.
New to recursion? Read Recursion Basics first.
The template
solve(state):
if state is a complete answer: record it; return
for each choice available now:
if choice is not allowed: skip ← pruning
make the choice (choose)
solve(next state) (explore)
undo the choice (un-choose)
Subsets (power set)
Each element is either taken or not taken → 2ⁿ subsets.
void subsets(vector<int>& a, int i, vector<int>& cur, vector<vector<int>>& out) {
if (i == a.size()) { out.push_back(cur); return; }
cur.push_back(a[i]); // take
subsets(a, i + 1, cur, out);
cur.pop_back(); // undo
subsets(a, i + 1, cur, out); // don't take
}
Time: O(2ⁿ · n) (2ⁿ subsets, copying each costs up to n).
With duplicates ([1,2,2]): sort first, and in a loop-based version skip a[i] == a[i-1] when i > start.
Permutations
Pick any unused element for the next position → n! permutations.
void permute(vector<int>& a, vector<bool>& used, vector<int>& cur, vector<vector<int>>& out) {
if (cur.size() == a.size()) { out.push_back(cur); return; }
for (int i = 0; i < a.size(); i++) {
if (used[i]) continue;
used[i] = true; cur.push_back(a[i]);
permute(a, used, cur, out);
used[i] = false; cur.pop_back();
}
}
Time: O(n! · n).
Combination sum
Numbers can be reused; stop when the sum passes the target.
void comb(vector<int>& c, int start, int target, vector<int>& cur, vector<vector<int>>& out) {
if (target == 0) { out.push_back(cur); return; }
for (int i = start; i < c.size(); i++) {
if (c[i] > target) continue; // prune (break if c is sorted)
cur.push_back(c[i]);
comb(c, i, target - c[i], cur, out); // i, not i + 1: reuse allowed
cur.pop_back();
}
}
N-Queens
Place one queen per row; a column or diagonal can hold only one queen.
int n; vector<string> board; vector<vector<string>> res;
vector<bool> col, d1, d2; // d1: r + c, d2: r - c + n - 1
void place(int r) {
if (r == n) { res.push_back(board); return; }
for (int c = 0; c < n; c++) {
if (col[c] || d1[r + c] || d2[r - c + n - 1]) continue;
col[c] = d1[r + c] = d2[r - c + n - 1] = true; board[r][c] = 'Q';
place(r + 1);
col[c] = d1[r + c] = d2[r - c + n - 1] = false; board[r][c] = '.';
}
}
The three boolean arrays make each check O(1) — that is pruning in action.
Other classics
| Problem | Choice at each step |
|---|---|
| Letter combinations of a phone number | which letter for this digit |
| Palindrome partitioning | where to cut next (only if the piece is a palindrome) |
| Generate parentheses | add ( if open < n, ) if close < open |
| Word search in a grid | which neighbour to step to (mark visited, unmark after) |
| Sudoku solver | which digit for the next empty cell |
| Rat in a maze | which direction to move |
Pruning makes it fast
- Stop as soon as a partial answer cannot work (sum > target, conflict in N-Queens).
- Sort the input so you can
breakinstead ofcontinue. - Keep O(1) checks with helper arrays/sets.
Complexity cheat sheet
| Problem | Answers | Time |
|---|---|---|
| Subsets | 2ⁿ | O(n · 2ⁿ) |
| Permutations | n! | O(n · n!) |
| Combinations C(n, k) | C(n, k) | O(k · C(n, k)) |
| N-Queens | — | O(n!) upper bound |
Practise in the Recursion & Backtracking section.
Interview one-liners
- Backtracking = DFS on the tree of choices + undo.
- If many sub-problems repeat, it is a DP problem instead — add memoisation.
- Always say the complexity in terms of the number of answers (2ⁿ, n!).
- Pass vectors by reference and undo changes, instead of copying at every call.