Om's Brain

6. Backtracking

29 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>& collect, vector<vector<int>>& result) {
    if (idx == arr.size()) {           // 🛑 Processed all elements
        result.push_back(collect);
        return;
    }
 
    collect.push_back(arr[idx]);       // ✅ Take
    solve(arr, idx + 1, collect, result);
    collect.pop_back();                // ↩️ Undo take
 
    solve(arr, idx + 1, collect, 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>& collect, vector<vector<int>>& result) {
    result.push_back(collect);             // Collect at every node (for subsets)
 
    for (int i = start; i < arr.size(); i++) {
        collect.push_back(arr[i]);         // 1️⃣ Choose
        backtrack(arr, i + 1, collect, result); // 2️⃣ Explore
        collect.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

⚡ Quick Complexity Guide

Here is the intuitive breakdown of backtracking time and space complexities.

1. Subsets (Power Set)

  • Time Complexity: O(2^N)
    • Why? There are N numbers and for each number, you make 2 decisions (either take or not take).
      • Example: for [1,2,3] you have 2 * 2 * 2 = 2^3 = 8 subsets. For N numbers, this generates 2^N subsets.
  • Space Complexity: O(N)
    • Max depth of the recursion tree is N (the number of elements).

2. Combinations (Choose R out of N)

  • Time Complexity: O(nCr)
    • Why? The total number of valid combination leaves is given by the combinations formula nCr (for example, choosing 2 elements out of N is nC2).
  • Space Complexity: O(R)
    • Recursion depth is capped at R since we stop as soon as we collect R elements.

3. Permutations (Arrangements)

  • Time Complexity: O(N * N!)
    • Why? For the 1st position you have N choices, for the 2nd you have N-1, then N-2, all the way down to 1 choice. This generates N! permutations.
      • We multiply by N because at each recursive step, we run a for-loop to iterate over all N candidates to see if they are visited.
  • Space Complexity: O(N)
    • Recursion stack goes up to depth N.

4. Grid Search / Maze (4-Directions DFS)

  • Time Complexity: O(4^L) or O(3^L)
    • Why? At any cell, you can step in 4 directions (Up, Down, Left, Right). For a path of length L, this creates 4^L potential paths. (If you cannot step back to where you just came from, it reduces to 3^L).
  • Space Complexity: O(L)
    • Recursion stack is equal to the length of the path L.

✂️ Pruning — What Separates Backtracking From Brute Force

Brute force walks the entire decision tree. Backtracking cuts branches that provably can’t succeed. Every pruning trick in this note is one of three levers — learn to spot which one a problem hands you.

The pruning mindset

Before every recursive call, ask: “Is there any way this branch leads to a valid answer?” If provably not, return right now. The closer to the root you prune, the more of the tree you delete — a cut at depth 2 can erase millions of leaves at depth 20.

LeverQuestion it answersExamples in this note
Feasibility”Can this partial state still become valid?”if (target < 0) return; (Combination Sum), isValid(...) (N-Queens, Sudoku), curr + nums[i] > target (K-Subsets)
Bound”Even in the best case, can I still reach the goal?”if (sum > k) return; (positives only), “remaining elements < needed” (Combinations), if (curr == 0) break; (K-Subsets)
Symmetry / Duplicate”Have I already explored an equivalent branch?“sort + skip equal siblings (Subsets II, Combination Sum II), frequency map (Permutations II)

6️⃣ 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 collect 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>& collect) {
        if (i == arr.size()) {
            ans.push_back(collect);
            return;
        }
 
        // ✅ Take
        collect.push_back(arr[i]);
        solve(arr, i + 1, collect);
        collect.pop_back();
 
        // ❌ Not take
        solve(arr, i + 1, collect);
    }
 
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<int> collect;
        solve(nums, 0, collect);
        return ans;
    }
};
// TC - O(n * 2^n) | SC - O(n) recursion depth

Subsets II (With Duplicates) — LC 90 💀

Good Follow Up: 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.

The Problem:

The soluation: If we not take 2 then don’t take for future dublicate as well or it will give you same results which already came previously

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

7️⃣ Pattern 2 — Combinations

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

Combinations — LC 77 ⭐

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

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

Combination Sum — LC 39 ⭐

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

// LC 39. Combination Sum (Take / Not-Take)
class Solution {
public:
    vector<vector<int>> ans;
 
    void solve(vector<int>& arr, int i, int target, vector<int>& collect) {
        if (target == 0) {
            ans.push_back(collect);
            return;
        }
        if (i == arr.size() || target < 0) return;
 
        // ✅ Take (stay at i — can reuse)
        collect.push_back(arr[i]);
        solve(arr, i, target - arr[i], collect);
        collect.pop_back();
 
        // ❌ Not take (move to next)
        solve(arr, i + 1, target, collect);
    }
 
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> collect;
        solve(candidates, 0, target, collect);
        return ans;
    }
};
// 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)

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)
class Solution {
public:
    vector<vector<int>> ans;
 
    void solve(vector<int>& arr, int i, int target, vector<int>& collect) {
        if (target == 0) {
            ans.push_back(collect);
            return;
        }
        if (i == arr.size() || target < 0) return;
 
        // ✅ Take
        collect.push_back(arr[i]);
        solve(arr, i + 1, target - arr[i], collect);
        collect.pop_back();
 
        // ⚠️ Skip duplicates for Not-Take branch
        while (i + 1 < arr.size() && arr[i] == arr[i + 1]) {
            i++;
        }
 
        // ❌ Not take
        solve(arr, i + 1, target, collect);
    }
 
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());  // ⚠️ MUST sort
        vector<int> collect;
        solve(candidates, 0, target, collect);
        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)
class Solution {
public:
    vector<vector<int>> ans;
 
    void solve(int i, int k, int remain, vector<int>& collect) {
        if (collect.size() == k && remain == 0) {
            ans.push_back(collect);
            return;
        }
        if (collect.size() >= k || remain < 0 || i > 9) return;
 
        // ✅ Take
        collect.push_back(i);
        solve(i + 1, k, remain - i, collect);
        collect.pop_back();
 
        // ❌ Not take
        solve(i + 1, k, remain, collect);
    }
 
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<int> collect;
        solve(1, k, n, collect);
        return ans;
    }
};
// 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

8️⃣ 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: Use unordered set for Visited Element or Mark the Original Array Element As visisted

// 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!) | SC - O(n)

Approach 2: Swap in place — the cleanest permutation code. Fix one position at a time by swapping each remaining element into it. No visited[], no extra array, no collect — nums itself is the answer when every position is fixed.

// LC 46. Permutations (Swap — O(1) extra state)
class Solution {
public:
    vector<vector<int>> ans;
 
    void solve(vector<int>& nums, int idx) {
        if (idx == nums.size()) {          // every position fixed → one permutation
            ans.push_back(nums);
            return;
        }
        for (int i = idx; i < nums.size(); i++) {
            swap(nums[idx], nums[i]);      // ✅ Choose: fix nums[i] at position idx
            solve(nums, idx + 1);          // 🔎 Explore the rest
            swap(nums[idx], nums[i]);      // ↩️ Unchoose: restore original order
        }
    }
 
    vector<vector<int>> permute(vector<int>& nums) {
        solve(nums, 0);
        return ans;
    }
};
// TC - O(n * n!) | SC - O(n) recursion only (no visited[] / no temp array)

Three ways to permute — pick one

  • visited set / INT_MAX marking — most explicit, easy to read.
  • swap in place — least memory, but note it does not produce permutations in sorted order and breaks the simple duplicate-skip trick (a swap can bring an already-seen value back).
  • frequency map (below) — the natural choice the moment duplicates appear.

Permutations II (With Duplicates) — LC 47 🔥

Input may have duplicates. Return only unique permutations.

Approach: Frequency Map

By building a frequency map of elements, we naturally avoid duplicates because we iterate over the unique keys of the map rather than indices of the array.

// LC 47. Permutations II (Frequency Map Approach)
class Solution {
public:
    vector<vector<int>> ans;
 
    void solve(unordered_map<int, int> &um, vector<int> &collect, int n) {
        if (collect.size() == n) {
            ans.push_back(collect);
            return;
        }
 
        for (auto &i : um) {
            int cnt = i.second;
            if (cnt != 0) {
                um[i.first]--;
                collect.push_back(i.first);
 
                solve(um, collect, n); // Explore
 
                collect.pop_back();    // Backtrack
                um[i.first]++;
            }
        }
    }
 
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        unordered_map<int, int> um;
        vector<int> collect;
        int n = nums.size();
        for (auto &i : nums) um[i]++;
 
        solve(um, collect, n);
        return ans;
    }
};
// TC - O(n!) | SC - O(n)

Alternative — sort + used[] (the editorial favorite)

Sort first, then at each level skip a value that equals its left neighbor when that neighbor isn’t currently used — meaning we’re at the same tree level and already tried it.

sort(nums.begin(), nums.end());
// inside the for-loop over i:
if (used[i]) continue;                                   // already placed on this path
if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue; // dup sibling → skip

The subtle part is !used[i-1]: if the previous equal element is used, the duplicates are on the same path (allowed); if it’s not used, they’re sibling branches (a duplicate — skip). Same idea as the sort-and-skip trick in Subsets II, applied per level.

9️⃣ 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)

Restore IP Addresses — LC 93 📍

Insert 3 dots into a digit string so it forms 4 valid octets (0-255, no leading zeros). Return all valid IPs.

Intuition: same “try every split” idea as Palindrome Partitioning, but with a fixed number of parts (4) and a validity rule per segment. Each cut takes 1-3 digits; prune the instant a segment is invalid.

// LC 93. Restore IP Addresses
class Solution {
public:
    vector<string> ans;
 
    // start = position in s, parts = octets placed, cur = IP built so far
    void solve(string& s, int start, int parts, string cur) {
        if (parts == 4) {
            if (start == s.size())
                ans.push_back(cur.substr(0, cur.size() - 1));  // drop trailing '.'
            return;                                            // used 4 parts, stop either way
        }
        for (int len = 1; len <= 3 && start + len <= s.size(); len++) {
            string seg = s.substr(start, len);
            if (len > 1 && seg[0] == '0') break;   // ⛔ leading zero → this and longer are invalid
            if (stoi(seg) > 255) break;            // ⛔ octet out of range
            solve(s, start + len, parts + 1, cur + seg + ".");
        }
    }
 
    vector<string> restoreIpAddresses(string s) {
        if (s.size() < 4 || s.size() > 12) return {};   // 4..12 digits or impossible
        solve(s, 0, 0, "");
        return ans;
    }
};
// TC - O(3^4) — at most 3 choices × 4 parts | SC - O(1) depth

Fixed-count partitioning

Palindrome Partitioning splits into an unknown number of parts; Restore IP splits into exactly 4. Carry a parts counter and make the base case check both “used all parts” and “consumed the whole string.” The break (not continue) on an invalid segment is a real prune — a longer segment can only be worse.

🔟 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️⃣1️⃣ 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.

Partition to K Equal Sum Subsets — LC 698 💀

Can nums be split into k subsets with equal sums? This is the problem where pruning is the difference between passing and TLE.

Idea: each subset must sum to total / k. Fill one bucket at a time up to target; when a bucket is full, recurse to build the next one. used[] tracks consumed elements.

// LC 698. Partition to K Equal Sum Subsets
class Solution {
public:
    vector<bool> used;
    int target, n;
 
    bool solve(vector<int>& nums, int k, int start, int curr) {
        if (k == 1) return true;                  // last bucket auto-balances
        if (curr == target)                       // bucket full → start the next one
            return solve(nums, k - 1, 0, 0);
        for (int i = start; i < n; i++) {
            if (used[i] || curr + nums[i] > target) continue;          // ✂️ feasibility
            if (i > start && nums[i] == nums[i-1] && !used[i-1]) continue; // ✂️ duplicate
            used[i] = true;
            if (solve(nums, k, i + 1, curr + nums[i])) return true;
            used[i] = false;
            if (curr == 0) break;   // ✂️ this num can't even START an empty bucket → hopeless
        }
        return false;
    }
 
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % k) return false;                // can't divide evenly
        target = sum / k; n = nums.size();
        used.assign(n, false);
        sort(nums.rbegin(), nums.rend());         // big elements first → prune sooner
        if (nums[0] > target) return false;       // one element already too big
        return solve(nums, k, 0, 0);
    }
};
// TC - O(k * 2^n) worst case, heavily pruned | SC - O(n)

All three pruning levers in one problem

This is the showcase for the pruning table above: feasibility (curr + nums[i] > target), duplicate (skip equal siblings), and a clever bound prune — if the current element can’t start an empty bucket (curr == 0), no arrangement ever will, so bail out entirely. Sorting descending makes all three fire earlier.

🧠 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 + while loop index skip: `while (i+1 < size && arr[i] == arr[i+1]) i++;`
└── Permutations → Use Frequency Map (`unordered_map<int, int> um`) to naturally avoid duplicate paths

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
”Split string into valid parts” (IP addr)Fixed-count partitioning + validity
”Word search in grid”Grid backtracking — 4-dir DFS
”N-Queens” / “Sudoku”Constraint satisfaction — prune hard
”Split into k equal-sum groups”Bucket fill + all 3 pruning levers

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. Did duplicate skipping on the Take branch instead of the Not-Take branch → skips valid branches
3. Forgot to check array boundaries in the duplicate skipping while loop (`i + 1 < size`) → out of bounds crash
4. Forgot to unchoose → entire tree is corrupted
5. Permutations: loop from start instead of 0 → missing permutations
6. Grid: forgot to restore cell after DFS → later paths wrongly blocked
7. Sudoku: forgot "return false" after trying all 9 digits → no backtracking
8. Passing vector by value when you mean by reference → unchoose not needed but O(n) copy per call. Know the trade-off.
9. Fixed-count partition (Restore IP): base case checks only "parts used" but forgets "whole string consumed" → accepts short IPs.
10. Swap-based permutations combined with the sort-and-skip dedup → swaps destroy the sorted order, so the dedup silently fails. Use a frequency map or `used[]` for duplicates.

1 item under this folder.

Mindmap

Graph View

Backlinks