Om's Brain

6. Backtracking

23 min read

1️⃣ Core Idea

Explore all possibilities. Choose → Explore → Unchoose.

Backtracking is controlled recursion. Instead of blindly generating everything, we build solutions one decision at a time, and the moment a partial solution can never lead to a valid answer, we abandon it (backtrack) and try the next option.

Why Backtracking?

Brute force generates ALL possible combinations, then filters valid ones. Backtracking prunes invalid branches EARLY → explores only what’s necessary. Think of it as DFS on an implicit decision tree where bad branches get cut.

2️⃣ When to Think Backtracking 🚀

✔️ Strong Signals

  • “Generate all subsets / combinations / permutations”
  • “Find all valid configurations” (N-Queens, Sudoku)
  • “All ways to partition / split”
  • “Generate all valid parentheses”
  • “Word search in a grid”
  • Output is a list of lists

✔️ Constraint Check

  • Input size is small (n ≤ 20 for exponential, n ≤ 10 for factorial)
  • The problem asks for exhaustive enumeration, not just count or optimal
  • There are constraints that let you prune (not just raw brute force)

Backtracking vs DP

  • Backtracking: “Give me ALL valid answers” → enumerate
  • DP: “Give me the COUNT or OPTIMAL answer” → optimize

Sometimes backtracking + memoization = DP (top-down). But pure backtracking problems rarely need memo since test sizes are small.

3️⃣ Two Ways to Think About Backtracking

There are two equivalent mental models. Pick the one that clicks for you.

Style 1 — Take / Not-Take (Binary Decision Tree) ✅ Preferred

At each index, ask: “Should I take this element or not take it?” This creates a binary tree — every node has exactly 2 children.

┌──────────────────────────────────────────────────┐
│        TAKE / NOT-TAKE SKELETON                  │
│                                                  │
│   At each index:                                 │
│   1. TAKE     → Include element, recurse         │
│   2. NOT TAKE → Exclude element, recurse          │
│                                                  │
│   + BASE CASE → index == size → record answer    │
│   + PRUNING   → Skip branches that can't work    │
└──────────────────────────────────────────────────┘

void solve(vector<int>& arr, int idx, vector<int>& current, vector<vector<int>>& result) {
    if (idx == arr.size()) {           // 🛑 Processed all elements
        result.push_back(current);
        return;
    }
 
    current.push_back(arr[idx]);       // ✅ Take
    solve(arr, idx + 1, current, result);
    current.pop_back();                // ↩️ Undo take
 
    solve(arr, idx + 1, current, result); // ❌ Not take
}

Style 2 — For-Loop (Multi-way Branching)

At each level, loop through all remaining candidates and try each one. Creates an n-ary tree — each node can have many children.

void backtrack(vector<int>& arr, int start, vector<int>& current, vector<vector<int>>& result) {
    result.push_back(current);             // Collect at every node (for subsets)
 
    for (int i = start; i < arr.size(); i++) {
        current.push_back(arr[i]);         // 1️⃣ Choose
        backtrack(arr, i + 1, current, result); // 2️⃣ Explore
        current.pop_back();                // 3️⃣ Unchoose
    }
}

When to use which?

  • Take/Not-Take is simpler to reason about — always 2 branches, base case at idx == n
  • For-Loop is more natural when you need to iterate over variable-length candidate lists (e.g., phone digits, variable choices per position)
  • Both produce the same results for subsets/combinations. Pick one and stick with it.

The Golden Rule of Backtracking

After the recursive call returns, the state MUST be exactly as it was before the call. This is why we push_back then pop_back, swap then swap back, mark then unmark, pick then unpick If you forget to unchoose, your entire recursion tree is corrupted.

4️⃣ Three Kinds of Recursion Questions

The same take/not-take tree can answer three different types of questions — the only thing that changes is the return type and base case.

Kind 1 — Print All (void)

Explore the entire tree. Collect every valid answer.

void solve(vector<int>& arr, int idx, vector<int>& ds, int sum, int k) {
    if (idx == arr.size()) {
        if (sum == k)
            result.push_back(ds);   // ✅ Found one — record it
        return;                     // Keep going, don't stop
    }
 
    ds.push_back(arr[idx]);                           // Take
    solve(arr, idx + 1, ds, sum + arr[idx], k);
    ds.pop_back();                                    // Undo
 
    solve(arr, idx + 1, ds, sum, k);                  // Not take
}

Kind 2 — Print One (bool) ⚡

Stop the moment you find the first valid answer. Huge time saving.

bool solve(vector<int>& arr, int idx, vector<int>& ds, int sum, int k) {
    if (idx == arr.size()) {
        if (sum == k) {
            print(ds);
            return true;     // ✅ Found — signal to stop
        }
        return false;        // ❌ Not valid — keep searching
    }
 
    ds.push_back(arr[idx]);
    if (solve(arr, idx + 1, ds, sum + arr[idx], k))  // Take
        return true;         // 🛑 Answer found downstream — stop!
    ds.pop_back();
 
    if (solve(arr, idx + 1, ds, sum, k))              // Not take
        return true;         // 🛑 Answer found downstream — stop!
 
    return false;            // Neither branch found anything
}

The bool Pattern

if (recursive_call() == true) return true;
if (recursive_call() == true) return true;
return false;

As soon as any branch returns true, every parent immediately returns true — the recursion unwinds instantly without exploring the remaining tree.

Kind 3 — Count (int)

Don’t print anything. Just count how many valid subsequences exist.

int solve(vector<int>& arr, int idx, int sum, int k) {
    if (idx == arr.size()) {
        if (sum == k)
            return 1;   // ✅ This path is valid — count it
        return 0;        // ❌ Not valid — contributes 0
    }
 
    int left  = solve(arr, idx + 1, sum + arr[idx], k); // Take
    int right = solve(arr, idx + 1, sum, k);             // Not take
 
    return left + right;  // Total = sum of both branches
}

The Count Pattern 

return 1;       ← valid path
return 0;       ← invalid path
left + right;   ← parent adds counts from both children

This is the foundation of DP. Add memoization to this and you get top-down DP.

📋 Quick Reference

Question asks…Return TypeBase CaseHow it stops
Print all answersvoidif (sum == k) → push to resultExplores entire tree
Print one answerboolreturn true / return falseStops on first true
Count answersintreturn 1 / return 0left + right at every node

🔥 Optimization (Positive Numbers Only)

If all elements are positive, you can prune early:

if (sum > k) return;     // (for void)
if (sum > k) return 0;   // (for int)

Once sum exceeds k, it can never decrease — no point exploring further.

5️⃣ The Three Problem Families

Almost every backtracking problem falls into one of three families.

FamilyTake/Not-Take StyleBase CaseOrder Matters?
SubsetsTake or skip each elementidx == n → collectNo
CombinationsTake or skip, but stop early at size ksize == k → collectNo
PermutationsEvery unused element can go at each positionsize == n → collectYes

Take / Not-Take Decision Tree (Subsets of [1, 2, 3])

                        idx=0
                      /       \
                 Take 1       Not take 1
                /     \        /     \
           Take 2  Not take  2  Take 2  Not take 2
           /   \      |       |       |
        T3  NT3  T3  NT3    T3 NT3  T3 NT3
        ↓   ↓    ↓    ↓     ↓   ↓    ↓   ↓
     {1,2,3}{1,2}{1,3}{1}  {2,3}{2} {3} {}

     ↑ Collect at EVERY leaf (idx == n) → 2^n subsets

Key Insight

  • Subsets: Collect at every leaf — each path through the binary tree is one subset
  • Combinations: Same tree, but prune branches where size > k or remaining elements < needed
  • Permutations: Can’t use take/not-take directly — use for-loop + visited[] or swap instead, because order matters and every element must appear

6️⃣ Handling Duplicates — The #1 Pitfall

When input has duplicate elements, raw backtracking generates duplicate results. Two universal fixes:

Fix 1: Sort + Skip (Most Common)

sort(nums.begin(), nums.end());  // MUST sort first
 
for (int i = start; i < n; i++) {
    // Skip duplicate at the SAME LEVEL of recursion
    if (i > start && nums[i] == nums[i - 1]) continue;
 
    current.push_back(nums[i]);
    backtrack(i + 1, ...);
    current.pop_back();
}

Fix 2: Frequency Map (For Permutations with Duplicates)

unordered_map<int, int> freq;
for (int x : nums) freq[x]++;
 
void backtrack(map, current, result) {
    for (auto& [num, count] : freq) {
        if (count == 0) continue;
        count--;
        current.push_back(num);
        backtrack(...);
        current.pop_back();
        count++;
    }
}

Why i > start and NOT i > 0?

i > 0 would skip valid choices at deeper recursion levels. i > start only skips duplicates at the same level — the same branching point. This is the single most common mistake in backtracking.

7️⃣ Pattern 1 — Subsets

These problems collect results at every leaf of the take/not-take decision tree.

Subsets — LC 78 🔥 📍

Given an array of distinct integers, return all possible subsets (the power set).

Intuition: At each element, we have 2 choices: take or not take. When we’ve processed all elements (i == n), whatever is in current is one valid subset.

// LC 78. Subsets (Take / Not-Take)
class Solution {
public:
    vector<vector<int>> ans;
    
    void solve(vector<int>& arr, int i, vector<int>& current) {
        if (i == arr.size()) {
            ans.push_back(current);
            return;
        }
 
        // ✅ Take
        current.push_back(arr[i]);
        solve(arr, i + 1, current);
        current.pop_back();
 
        // ❌ Not take
        solve(arr, i + 1, current);
    }
    
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<int> current;
        solve(nums, 0, current);
        return ans;
    }
};
// TC - O(n * 2^n) | SC - O(n) recursion depth

Subsets II (With Duplicates) — LC 90 🔥

Same as Subsets but input may contain duplicates. Result must not have duplicate subsets.

Intuition: Sort first. Then at each level, if we decide to Not Take the current element, we must skip all subsequent elements that are equal to it to avoid generating duplicate branches.

// LC 90. Subsets II (Take / Not-Take)
class Solution {
public:
    vector<vector<int>> ans;
    
    void solve(vector<int> &nums, vector<int> &ss, int i) {
        if (i == nums.size()) {
            ans.push_back(ss);
            return;
        }
 
        // ✅ Take
        ss.push_back(nums[i]);
        solve(nums, ss, i + 1);
        ss.pop_back();
 
        // ⚠️ Skip duplicates for the Not-Take branch
        while (i + 1 < nums.size() && nums[i] == nums[i + 1]) {
            i++;
        }
 
        // ❌ Not take
        solve(nums, ss, i + 1);
    }
    
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<int> ss;
        sort(nums.begin(), nums.end());  // ⚠️ MUST sort
        solve(nums, ss, 0);
        return ans;
    }
};
// TC - O(n * 2^n) | SC - O(n)

8️⃣ Pattern 2 — Combinations

Same take/not-take structure as subsets, but we only collect results when current.size() == k.

Combinations — LC 77 🔥

Return all combinations of k numbers from [1, n].

// LC 77. Combinations (Take / Not-Take)
vector<vector<int>> combine(int n, int k) {
    vector<vector<int>> result;
    vector<int> current;
    solve(1, n, k, current, result);
    return result;
}
 
void solve(int idx, int n, int k, vector<int>& current, vector<vector<int>>& result) {
    if (current.size() == k) {       // Collected k elements → record
        result.push_back(current);
        return;
    }
    if (idx > n) return;             // No more elements to consider
 
    current.push_back(idx);          // ✅ Take idx
    solve(idx + 1, n, k, current, result);
    current.pop_back();              // ↩️ Undo
 
    solve(idx + 1, n, k, current, result); // ❌ Not take idx
}
// TC - O(k * C(n,k)) | SC - O(k)

Pruning Optimization

If remaining elements < elements still needed, prune early:

for (int i = start; i <= n - (k - current.size()) + 1; i++)

This avoids exploring branches that can never produce k elements.

Combination Sum — LC 39 🔥 📍

Find all unique combinations where candidate numbers sum to target. Same number can be reused.

Key insight: Since we CAN reuse, “take” doesn’t advance the index — we stay at idx to allow taking it again. Only “not take” moves to idx + 1.

// LC 39. Combination Sum (Take / Not-Take)
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> result;
    vector<int> current;
    solve(candidates, 0, target, current, result);
    return result;
}
 
void solve(vector<int>& arr, int idx, int remain, vector<int>& current, vector<vector<int>>& result) {
    if (remain == 0) {
        result.push_back(current);
        return;
    }
    if (idx == arr.size() || remain < 0) return;
 
    current.push_back(arr[idx]);                  // ✅ Take (stay at idx — can reuse)
    solve(arr, idx, remain - arr[idx], current, result);
    current.pop_back();                           // ↩️ Undo
 
    solve(arr, idx + 1, remain, current, result); // ❌ Not take (move to next)
}
// TC - O(n^(target/min)) | SC - O(target/min)

Take stays, Not-Take moves

Reuse allowed: Take → idx, Not-Take → idx + 1 No reuse: Take → idx + 1, Not-Take → idx + 1 (same as subsets) This single difference is what separates Combination Sum from regular Combinations.

Combination Sum II (No Reuse + Duplicates) — LC 40 🔥

Each number used at most once. Input may contain duplicates.

Combines both techniques: No reuse means Take moves to idx + 1. Duplicates means Not-Take must skip identical elements.

// LC 40. Combination Sum II (Take / Not-Take, Backwards Iteration)
class Solution {
public:
    vector<vector<int>> ans;
    
    void solve(vector<int>& candidates, vector<int>& collect, int target, int i) {
        if (target == 0) {
            ans.push_back(collect);
            return;
        }
        if (target < 0 || i < 0) return;
 
        // ✅ Take 
        collect.push_back(candidates[i]);
        solve(candidates, collect, target - candidates[i], i - 1);
        collect.pop_back();
 
        // ⚠️ Skip duplicates for Not-Take branch
        while (i - 1 >= 0 && candidates[i] == candidates[i - 1]) {
            i--;
        }
 
        // ❌ Not take
        solve(candidates, collect, target, i - 1);
    }
    
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());  // ⚠️ MUST sort
        vector<int> collect;
        solve(candidates, collect, target, candidates.size() - 1); // Start from end
        return ans;
    }
};
// TC - O(2^n) | SC - O(n)

Combination Sum III — LC 216 ⭐

Find all combinations of k numbers from 1-9 that sum to n.

// LC 216. Combination Sum III (Take / Not-Take)
vector<vector<int>> combinationSum3(int k, int n) {
    vector<vector<int>> result;
    vector<int> current;
    solve(1, k, n, current, result);
    return result;
}
 
void solve(int idx, int k, int remain,
           vector<int>& current, vector<vector<int>>& result) {
    if (current.size() == k && remain == 0) {
        result.push_back(current);
        return;
    }
    if (current.size() >= k || remain < 0 || idx > 9) return;
 
    // ✅ Take
    current.push_back(idx);
    solve(idx + 1, k, remain - idx, current, result);
    current.pop_back();
 
    // ❌ Not take
    solve(idx + 1, k, remain, current, result);
}
// TC - O(C(9,k)) | SC - O(k)

📋 Combination Family Cheatsheet

ProblemReuse?Duplicates?Pass to recurseExtra
Combination Sum✅❌i—
Combination Sum II❌✅i+1Sort + skip dupes
Combination Sum III❌❌i+1Fixed range 1-9
Combinations❌❌i+1Stop at size k

9️⃣ Pattern 3 — Permutations

In permutations, order matters. {1,2,3} and {3,2,1} are different permutations.

Key difference from subsets/combinations: The loop starts from 0 (not start) because every element can appear at any position.

Permutations — LC 46 🔥 📍

Return all permutations of an array of distinct integers.

Approach 1: Visited Array — Most intuitive

// LC 46. Permutations (In-place INT_MAX visited approach)
class Solution {
public:
    vector<vector<int>> ans;
    
    void solve(vector<int>& nums, vector<int>& tem) {
        if (tem.size() == nums.size()) {  // All elements placed
            ans.push_back(tem);
            return;
        }
 
        for (auto& i : nums) {            // ← loops through all elements
            if (i != INT_MAX) {           // ← INT_MAX means visited
                int store = i;
                tem.push_back(i);
                i = INT_MAX;              // Mark as visited (Choose)
 
                solve(nums, tem);         // Explore
 
                i = store;                // Unmark (Unchoose)
                tem.pop_back();
            }
        }
    }
    
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> tem;
        solve(nums, tem);
        return ans;
    }
};
// TC - O(n * n!) | SC - O(n)

Approach 2: Swap — More space efficient

// LC 46. Permutations (swap approach)
vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> result;
    backtrack(nums, 0, result);
    return result;
}
 
void backtrack(vector<int>& nums, int idx, vector<vector<int>>& result) {
    if (idx == nums.size()) {
        result.push_back(nums);
        return;
    }
 
    for (int i = idx; i < nums.size(); i++) {
        swap(nums[i], nums[idx]);              // Choose: put nums[i] at position idx
        backtrack(nums, idx + 1, result);       // Explore
        swap(nums[i], nums[idx]);              // Unchoose: restore
    }
}
// TC - O(n * n!) | SC - O(n) recursion only

Swap Approach Intuition

At each position idx, we try every remaining element by swapping it into that position. After recursion, we swap back to restore the array for the next iteration. No extra used[] array or current vector needed!

Permutations II (With Duplicates) — LC 47 🔥

Input may have duplicates. Return only unique permutations.

Approach: Sort + Visited + Skip Rule

// LC 47. Permutations II
vector<vector<int>> permuteUnique(vector<int>& nums) {
    sort(nums.begin(), nums.end());  // ⚠️ Sort for dedup
    vector<vector<int>> result;
    vector<int> current;
    vector<bool> used(nums.size(), false);
    backtrack(nums, used, current, result);
    return result;
}
 
void backtrack(vector<int>& nums, vector<bool>& used,
               vector<int>& current, vector<vector<int>>& result) {
    if (current.size() == nums.size()) {
        result.push_back(current);
        return;
    }
 
    for (int i = 0; i < nums.size(); i++) {
        if (used[i]) continue;
 
        // Skip duplicate: same value as previous, and previous was NOT used
        // (meaning previous was already explored and backtracked at this level)
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
 
        used[i] = true;
        current.push_back(nums[i]);
        backtrack(nums, used, current, result);
        current.pop_back();
        used[i] = false;
    }
}
// TC - O(n * n!) | SC - O(n)

Why !used[i-1]?

When nums[i] == nums[i-1] and used[i-1] == false: It means nums[i-1] was tried and backtracked at this same recursion level. Using nums[i] now would generate the same branch → skip it.

This is the most confusing part of backtracking. Draw the recursion tree with [1,1,2] to see it.

🔟 Pattern 4 — String Generation

These problems generate strings character-by-character, with constraints on what character can come next.

Generate Parentheses — LC 22 🔥 📍

Generate all valid combinations of n pairs of parentheses.

Intuition: At each position, we have at most 2 choices:

  1. Add ( if we haven’t used all n opening brackets
  2. Add ) if closing count < opening count (ensures validity)
// LC 22. Generate Parentheses
vector<string> generateParenthesis(int n) {
    vector<string> result;
    backtrack(n, 0, 0, "", result);
    return result;
}
 
void backtrack(int n, int open, int close, string current, vector<string>& result) {
    if (current.size() == 2 * n) {  // Base: placed all 2n characters
        result.push_back(current);
        return;
    }
 
    if (open < n)                                   // Can still add (
        backtrack(n, open + 1, close, current + "(", result);
 
    if (close < open)                               // Can add ) only if < open
        backtrack(n, open, close + 1, current + ")", result);
}
// TC - O(4^n / √n) — nth Catalan number | SC - O(n)

Why No Explicit Unchoose?

We’re passing current + "(" as a new string (by value), not modifying current. So the original current is unchanged when we return — the unchoose happens automatically. This is a common shortcut with strings. Trade-off: more memory, but cleaner code.

Letter Combinations of a Phone Number — LC 17 🔥

Map each digit to its letters. Generate all possible letter combinations.

// LC 17. Letter Combinations of a Phone Number
vector<string> letterCombinations(string digits) {
    if (digits.empty()) return {};
 
    vector<string> phone = {"", "", "abc", "def", "ghi",
                            "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> result;
    backtrack(digits, phone, 0, "", result);
    return result;
}
 
void backtrack(string& digits, vector<string>& phone, int index,
               string current, vector<string>& result) {
    if (index == digits.size()) {  // Processed all digits
        result.push_back(current);
        return;
    }
 
    string& letters = phone[digits[index] - '0'];
    for (char c : letters) {
        backtrack(digits, phone, index + 1, current + c, result);
        // No unchoose needed — current + c creates a new string
    }
}
// TC - O(4^n) where n = digits.length | SC - O(n)

Palindrome Partitioning — LC 131 🔥

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

Intuition: At each position, try every possible substring starting there. If it’s a palindrome, take it as a partition and recurse on the rest.

// LC 131. Palindrome Partitioning
vector<vector<string>> partition(string s) {
    vector<vector<string>> result;
    vector<string> current;
    backtrack(s, 0, current, result);
    return result;
}
 
void backtrack(string& s, int start,
               vector<string>& current, vector<vector<string>>& result) {
    if (start == s.size()) {  // Partitioned the entire string
        result.push_back(current);
        return;
    }
 
    for (int end = start; end < s.size(); end++) {
        if (isPalindrome(s, start, end)) {
            current.push_back(s.substr(start, end - start + 1));  // Choose
            backtrack(s, end + 1, current, result);                // Explore
            current.pop_back();                                   // Unchoose
        }
    }
}
 
bool isPalindrome(string& s, int lo, int hi) {
    while (lo < hi) {
        if (s[lo++] != s[hi--]) return false;
    }
    return true;
}
// TC - O(n * 2^n) | SC - O(n)

1️⃣1️⃣ Pattern 5 — Grid / Board Search

These use backtracking on a 2D grid with in-place marking for visited cells.

Word Search — LC 79 🔥 📍

Given a 2D board and a word, check if the word exists by adjacent cells (no reuse).

Backtracking pattern on grids:

  1. Choose: mark cell as visited (e.g., board[r][c] = '#')
  2. Explore: try all 4 directions
  3. Unchoose: restore the original character
// LC 79. Word Search
bool exist(vector<vector<char>>& board, string word) {
    int rows = board.size(), cols = board[0].size();
 
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (backtrack(board, word, r, c, 0))
                return true;
        }
    }
    return false;
}
 
bool backtrack(vector<vector<char>>& board, string& word,
               int r, int c, int idx) {
    if (idx == word.size()) return true;  // Found all characters
 
    // Boundary check + character match
    if (r < 0 || r >= board.size() || c < 0 || c >= board[0].size()
        || board[r][c] != word[idx])
        return false;
 
    char saved = board[r][c];
    board[r][c] = '#';  // Choose: mark visited
 
    // Explore: 4 directions
    bool found = backtrack(board, word, r + 1, c, idx + 1)
              || backtrack(board, word, r - 1, c, idx + 1)
              || backtrack(board, word, r, c + 1, idx + 1)
              || backtrack(board, word, r, c - 1, idx + 1);
 
    board[r][c] = saved;  // Unchoose: restore
 
    return found;
}
// TC - O(m * n * 4^L) where L = word length | SC - O(L) recursion

In-Place Marking

We modify board[r][c] = '#' to mark it visited, then restore it. This avoids needing a separate visited[][] matrix. Some interviewers prefer the explicit visited matrix — both are valid.

1️⃣2️⃣ Pattern 6 — Constraint Satisfaction

These problems have hard constraints that make most of the search space invalid. Heavy pruning is the key.

N-Queens — LC 51 🔥 📍

Place n queens on an n×n board so no two queens attack each other.

Approach: Place queens row by row. For each row, try every column. Before placing, check if the column, left diagonal, or right diagonal is already occupied.

// LC 51. N-Queens
vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> result;
    vector<string> board(n, string(n, '.'));
    backtrack(board, 0, n, result);
    return result;
}
 
void backtrack(vector<string>& board, int row, int n,
               vector<vector<string>>& result) {
    if (row == n) {  // All queens placed
        result.push_back(board);
        return;
    }
 
    for (int col = 0; col < n; col++) {
        if (isValid(board, row, col, n)) {
            board[row][col] = 'Q';                      // Choose
            backtrack(board, row + 1, n, result);        // Explore next row
            board[row][col] = '.';                       // Unchoose
        }
    }
}
 
bool isValid(vector<string>& board, int row, int col, int n) {
    // Check column (rows above)
    for (int i = 0; i < row; i++)
        if (board[i][col] == 'Q') return false;
 
    // Check upper-left diagonal
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
        if (board[i][j] == 'Q') return false;
 
    // Check upper-right diagonal
    for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++)
        if (board[i][j] == 'Q') return false;
 
    return true;
}
// TC - O(n!) | SC - O(n²)

O(1) Validity Check with HashSets

Instead of scanning the board each time, maintain three sets:

  • cols — columns that have a queen
  • diag1 — left diagonals (row - col is constant along a left diagonal)
  • diag2 — right diagonals (row + col is constant along a right diagonal)
unordered_set<int> cols, diag1, diag2;
// isValid becomes: !cols.count(col) && !diag1.count(row-col) && !diag2.count(row+col)

Sudoku Solver — LC 37 💀

Fill in empty cells so every row, column, and 3×3 box contains digits 1-9.

// LC 37. Sudoku Solver
void solveSudoku(vector<vector<char>>& board) {
    backtrack(board);
}
 
bool backtrack(vector<vector<char>>& board) {
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            if (board[r][c] != '.') continue;  // Skip filled cells
 
            for (char num = '1'; num <= '9'; num++) {
                if (isValid(board, r, c, num)) {
                    board[r][c] = num;         // Choose
 
                    if (backtrack(board))       // Explore — if solved, stop!
                        return true;
 
                    board[r][c] = '.';         // Unchoose
                }
            }
            return false;  // No valid number → backtrack
        }
    }
    return true;  // All cells filled
}
 
bool isValid(vector<vector<char>>& board, int row, int col, char num) {
    for (int i = 0; i < 9; i++) {
        if (board[row][i] == num) return false;       // Row check
        if (board[i][col] == num) return false;       // Column check
 
        // 3x3 box check
        int boxRow = 3 * (row / 3) + i / 3;
        int boxCol = 3 * (col / 3) + i % 3;
        if (board[boxRow][boxCol] == num) return false;
    }
    return true;
}
// TC - O(9^(empty cells)) worst case, heavily pruned | SC - O(81)

Key Difference from N-Queens

Sudoku needs exactly one solution → we return true as soon as one is found. N-Queens collects all solutions → we don’t short-circuit. This return true / return false pattern is common in “find ONE valid configuration” problems.

🧠 Master Cheatsheet

The Decision Framework

What does the problem ask?
│
├── "All subsets / subsequences"
│   └── SUBSETS → Take/Not-Take, collect at every leaf (idx == n)
│
├── "All combinations of size k" or "that sum to target"
│   └── COMBINATIONS → Take/Not-Take, collect when size == k
│       ├── Can reuse?  → Take stays at idx,   Not-Take moves to idx+1
│       └── No reuse?   → Take moves to idx+1, Not-Take moves to idx+1
│
├── "All permutations / arrangements"
│   └── PERMUTATIONS → For-loop from 0, use visited[] or swap
│
├── "Generate valid strings" (parentheses, phone letters)
│   └── STRING GENERATION → constrained choices at each position
│
├── "Find word in grid / explore all paths"
│   └── GRID BACKTRACKING → in-place marking, 4-directional DFS
│
└── "Place queens / solve puzzle"
    └── CONSTRAINT SATISFACTION → heavy pruning, isValid check

Has duplicates?
├── Subsets / Combinations → sort + skip (i > start && nums[i] == nums[i-1])
└── Permutations → sort + skip (i > 0 && nums[i] == nums[i-1] && !used[i-1])

Pattern Recognition Table

Signal in problemPattern to use
”All subsets” / “power set”Take/Not-Take, collect at leaf
”All combinations of k elements”Take/Not-Take, stop at size k
”Numbers summing to target”Take/Not-Take, take stays at idx
”All permutations” / “all orderings”For-loop from 0, visited[] or swap
”Generate parentheses” / “valid strings”String generation — branching rules
”Partition into palindromes”Partitioning — try all splits
”Word search in grid”Grid backtracking — 4-dir DFS
”N-Queens” / “Sudoku”Constraint satisfaction — prune hard

The Three Key Tweaks (Take / Not-Take Style)

1. WHAT DOES "TAKE" DO?
   - No reuse:  Take → idx + 1  (move forward)
   - With reuse: Take → idx     (stay — can take again)

2. WHAT DOES "NOT TAKE" DO?
   - Always: Not-Take → idx + 1  (move to next element)

3. WHEN DOES TAKE/NOT-TAKE NOT WORK?
   - Permutations → order matters, every element must appear
   - Use For-Loop + visited[] or swap instead

Common Gotchas

1. Forgot to sort before deduplication → duplicates still appear
2. Used i > 0 instead of i > start → valid choices get skipped
3. Forgot to unchoose → entire tree is corrupted
4. Permutations: loop from start instead of 0 → missing permutations
5. Grid: forgot to restore cell after DFS → later paths wrongly blocked
6. Sudoku: forgot "return false" after trying all 9 digits → no backtracking
7. Passing vector by value when you mean by reference → unchoose not needed
   but O(n) copy per call. Know the trade-off.

1 item under this folder.

Mindmap

Graph View