Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

More DSA notes