Backtracking | Phase 3

Universal Backtracking Template

All backtracking problems follow the same structure. Fill in the three labeled sections.

C++
void backtrack(/* state */, vector<vector<int>>& result, vector<int>& current) {
    // BASE CASE — current is a complete valid solution
    if (/* done */) {
        result.push_back(current);
        return;
    }
    // ITERATE over all choices at this point
    for (int choice : /* candidates */) {
        // PRUNE — skip invalid choices
        if (/* invalid(choice) */) continue;

        // CHOOSE — add to current path
        current.push_back(choice);

        // EXPLORE — recurse with updated state
        backtrack(/* updated state */, result, current);

        // UN-CHOOSE — undo to restore state (backtrack!)
        current.pop_back();
    }
}
// The pattern is: choose → explore → un-choose
// Pruning is optional but critical for performance
    

Interactive: Backtracking Subsets

Watch backtracking generate subsets of [1, 2, 3]. Each step either chooses an element (highlighted) or backtracks (crossed). Every partial path is a valid subset.

Practice Problems

#78SubsetsMedium

Return all subsets (power set) of a list of unique integers.

Pattern: At each index, choose to include or not include it. Result is added at each level, not just leaf. Start from increasing index to avoid repeats.

C++
void bt(vector<int>& nums, int start, vector<int>& cur, vector<vector<int>>& res) {
    res.push_back(cur);  // every partial path is a valid subset
    for(int i=start; i<nums.size(); i++) {
        cur.push_back(nums[i]);
        bt(nums, i+1, cur, res);
        cur.pop_back();
    }
}
vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> res; vector<int> cur;
    bt(nums, 0, cur, res); return res;
}
// Time: O(2ⁿ)  Space: O(n)

#46PermutationsMedium

Return all permutations of distinct integers.

Pattern: At each step, pick any unused number. Use visited array or swap-based approach.

C++
void bt(vector<int>& nums, vector<bool>& used, vector<int>& cur, vector<vector<int>>& res) {
    if(cur.size()==nums.size()) { res.push_back(cur); return; }
    for(int i=0; i<nums.size(); i++) {
        if(used[i]) continue;
        used[i]=true; cur.push_back(nums[i]);
        bt(nums,used,cur,res);
        used[i]=false; cur.pop_back();
    }
}
vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> res;
    vector<int> cur; vector<bool> used(nums.size(),false);
    bt(nums,used,cur,res); return res;
}
// Time: O(n! * n)  Space: O(n)

#39Combination SumMedium

Find all combinations from candidates that sum to target. Same number can be used multiple times.

Pattern: Backtracking with same index allowed (not i+1). Prune when remaining < 0. Sort first for early termination.

C++
void bt(vector<int>& c, int start, int rem, vector<int>& cur, vector<vector<int>>& res) {
    if(rem==0) { res.push_back(cur); return; }
    for(int i=start; i<c.size() && c[i]<=rem; i++) {
        cur.push_back(c[i]);
        bt(c, i, rem-c[i], cur, res);  // i not i+1 (reuse allowed)
        cur.pop_back();
    }
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    sort(candidates.begin(),candidates.end());
    vector<vector<int>> res; vector<int> cur;
    bt(candidates,0,target,cur,res); return res;
}

#17Letter Combinations of a Phone NumberMedium

Given digits 2-9, return all possible letter combinations (T9 mapping).

Pattern: At each digit, try all mapped letters. Recurse on next digit.

C++
void bt(string& digits, int i, string& cur, vector<string>& res, vector<string>& mp) {
    if(i==digits.size()) { res.push_back(cur); return; }
    for(char c : mp[digits[i]-'2']) {
        cur.push_back(c);
        bt(digits,i+1,cur,res,mp);
        cur.pop_back();
    }
}
vector<string> letterCombinations(string digits) {
    if(digits.empty()) return {};
    vector<string> mp = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    vector<string> res; string cur;
    bt(digits,0,cur,res,mp); return res;
}

#79Word SearchMedium

Search for a word in a 2D grid. Letters must be adjacent (4-directional) and not reused.

Pattern: DFS backtracking on grid. Mark cell visited by overwriting, restore on backtrack. Prune immediately if letter doesn't match.

C++
bool dfs(vector<vector<char>>& g, string& w, int r, int c, int k) {
    if(k==w.size()) return true;
    if(r<0||r>=g.size()||c<0||c>=g[0].size()||g[r][c]!=w[k]) return false;
    char tmp=g[r][c]; g[r][c]='#';  // mark visited
    bool found = dfs(g,w,r+1,c,k+1)||dfs(g,w,r-1,c,k+1)||
                 dfs(g,w,r,c+1,k+1)||dfs(g,w,r,c-1,k+1);
    g[r][c]=tmp;  // restore
    return found;
}
bool exist(vector<vector<char>>& grid, string word) {
    for(int r=0;r<grid.size();r++)
        for(int c=0;c<grid[0].size();c++)
            if(dfs(grid,word,r,c,0)) return true;
    return false;
}
// Time: O(m*n*4^L)  Space: O(L)

#131Palindrome PartitioningMedium

Partition string s such that every substring is a palindrome. Return all such partitions.

Pattern: Backtracking where at each position we try all substrings starting here. If palindrome, add to path and recurse. Prune non-palindromes.

C++
bool isPalin(string& s, int l, int r) {
    while(l<r) if(s[l++]!=s[r--]) return false;
    return true;
}
void bt(string& s, int start, vector<string>& cur, vector<vector<string>>& res) {
    if(start==s.size()) { res.push_back(cur); return; }
    for(int end=start; end<s.size(); end++) {
        if(!isPalin(s,start,end)) continue;
        cur.push_back(s.substr(start,end-start+1));
        bt(s,end+1,cur,res);
        cur.pop_back();
    }
}
vector<vector<string>> partition(string s) {
    vector<vector<string>> res; vector<string> cur;
    bt(s,0,cur,res); return res;
}

#51N-QueensHard

Place n queens on n×n chessboard so no two queens attack each other. Return all valid arrangements.

Pattern: Place one queen per row. Track which columns, diagonals (row-col), and anti-diagonals (row+col) are occupied. Each row: try each column, skip if attacked.

C++
void bt(int n, int row, vector<string>& board,
         set<int>& cols, set<int>& diag, set<int>& anti,
         vector<vector<string>>& res) {
    if(row==n) { res.push_back(board); return; }
    for(int c=0;c<n;c++) {
        if(cols.count(c)||diag.count(row-c)||anti.count(row+c)) continue;
        board[row][c]='Q';
        cols.insert(c); diag.insert(row-c); anti.insert(row+c);
        bt(n,row+1,board,cols,diag,anti,res);
        board[row][c]='.';
        cols.erase(c); diag.erase(row-c); anti.erase(row+c);
    }
}
vector<vector<string>> solveNQueens(int n) {
    vector<string> board(n, string(n,'.'));
    vector<vector<string>> res;
    set<int> cols,diag,anti;
    bt(n,0,board,cols,diag,anti,res);
    return res;
}
// Time: O(n!)  Space: O(n)

Pruning is everything. The difference between TLE and AC is pruning. Before recursing, check if the current path can possibly lead to a valid answer. If not, return immediately.

Deeper Understanding

Why Backtracking Is Not Brute Force

Pruning Cuts the Search Space Exponentially

Brute force: try every possible assignment

For N-Queens on an 8×8 board: 8^8 = 16,777,216 candidate placements. Backtracking cuts this to ~15,000 nodes — a 1000× reduction from pruning invalid columns and diagonals early.

Pruning point: prune as early as possible

Check constraints before recursing, not after. If placing a queen at (row, col) is already invalid, don't recurse into that subtree at all — saves the entire sub-tree cost.

Constraint propagation (advanced)

After placing a queen, immediately mark its row, column, and diagonals as off-limits. This narrows candidates for future rows from N down to much fewer — the essence of sudoku solvers.

Classic Mistake: Forgetting to Un-choose

The bug: mutating state without restoring it

If you push_back(choice) before recursing but forget to pop_back() after, the cur vector accumulates all choices ever made — not just the current path. Each branch sees a polluted state.

The fix: always mirror choose with un-choose

Every mutation before the recursive call needs a matching undo after it. This is why the pattern is always: cur.push_back(x); bt(...); cur.pop_back(); — symmetric and explicit.

Global vs local state

Prefer passing cur by reference and restoring it. Passing by value (copying the path each call) is correct but O(n) space per level — fine for small n, but avoid when the path is large.

Recognizing When to Use Backtracking

Signal: "find all" or "enumerate all valid"

Subsets, permutations, combinations, all paths in a maze — any problem asking for an exhaustive list of solutions is a backtracking candidate.

Signal: constraint satisfaction

N-Queens, Sudoku, word search — problems where you must satisfy constraints at every step and a partial assignment can be declared invalid early.

Don't use if: optimal single answer, no enumeration needed

If you only need one optimal value (max profit, min cost), DP or greedy is better. Backtracking explores all possibilities — avoid if overlapping subproblems exist.