How To Solve ANY Backtracking Problem - Step By Step Guide Along With Problem Examples
Rochak Vyas
429
BacktrackingRecursionCareerInterview

Backtracking seemed like magic to me.

Then I realized every single backtracking problem uses
the same three steps — choose, explore, unchoose.
Once you see it, you can't unsee it.

Here is the complete guide.

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
THE CORE IDEA — THREE STEPS EVERY TIME
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Backtracking = build a solution step by step.
At each step: make a choice, explore it, then undo it.

void backtrack(state, choices) {
    if (goal reached) {
        result.push_back(state);   // record the solution
        return;
    }

    for (each valid choice) {
        make choice;        // add to state
        backtrack(...);     // explore deeper
        undo choice;        // restore state — this is the backtrack
    }
}

The undo step is what makes backtracking different from plain DFS.
You restore state so the next branch starts completely clean.

THINK OF IT LIKE A DECISION TREE:

Each node = a partial solution.
Each edge = one choice made.
Leaf = a complete solution (record it) or a dead end (prune it).
Backtracking = when you hit a leaf, climb back up and try the next edge.

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
THERE ARE 4 TYPES OF BACKTRACKING PROBLEMS ON LEETCODE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

TYPE 1 — SUBSETS → include or skip each element
TYPE 2 — PERMUTATIONS → arrange elements in every possible order
TYPE 3 — COMBINATIONS → pick elements to satisfy a condition
TYPE 4 — CONSTRAINTS → place elements satisfying hard rules (N-Queens, Sudoku)

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
TYPE 1 — SUBSETS
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

When to use:
→ Generate every possible subset of a set
→ Every element is either included or not

Key insight: at each index, two choices — include nums[i] or skip it.
Use a start index so you never go backwards (avoids duplicates).
Record the current state at EVERY level, not just the leaves.

TEMPLATE:

void backtrack(vector<int>& nums, int start,
               vector<int>& cur, vector<vector<int>>& res) {
    res.push_back(cur);              // every partial state is valid

    for (int i = start; i < nums.size(); i++) {
        cur.push_back(nums[i]);      // choose
        backtrack(nums, i+1, cur, res);  // explore (i+1 = no reuse)
        cur.pop_back();              // unchoose
    }
}

EXAMPLE — Subsets
https://leetcode.com/problems/subsets

vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> res;
    vector<int> cur;
    backtrack(nums, 0, cur, res);
    return res;
}

EXAMPLE — Subsets II (input has duplicates)
https://leetcode.com/problems/subsets-ii

Sort first. At the same recursion level, skip if nums[i] == nums[i-1].
This avoids generating the same subset twice.

void backtrack(vector<int>& nums, int start,
               vector<int>& cur, vector<vector<int>>& res) {
    res.push_back(cur);
    for (int i = start; i < nums.size(); i++) {
        if (i > start && nums[i] == nums[i-1]) continue;   // skip duplicate
        cur.push_back(nums[i]);
        backtrack(nums, i+1, cur, res);
        cur.pop_back();
    }
}

EXAMPLE — Palindrome Partitioning
https://leetcode.com/problems/palindrome-partitioning

At each position, try every possible prefix.
If it is a palindrome → include it and recurse on the rest.

void backtrack(string& s, int start, vector<string>& cur,
               vector<vector<string>>& res) {
    if (start == s.size()) { res.push_back(cur); return; }
    for (int end = start+1; end <= s.size(); end++) {
        string sub = s.substr(start, end-start);
        if (isPalindrome(sub)) {
            cur.push_back(sub);
            backtrack(s, end, cur, res);
            cur.pop_back();
        }
    }
}

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
TYPE 2 — PERMUTATIONS
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

When to use:
→ Generate all arrangements of elements
→ Order matters — [1,2,3] and [3,2,1] are different answers

Key difference from subsets:
Subsets use a start index (never go backward).
Permutations use a visited array (pick any unused element each step).

TEMPLATE:

void backtrack(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]);
        backtrack(nums, used, cur, res);
        cur.pop_back();
        used[i] = false;
    }
}

EXAMPLE — Permutations
https://leetcode.com/problems/permutations

Directly apply the template above.

EXAMPLE — Permutations II (input has duplicates)
https://leetcode.com/problems/permutations-ii

  // Sort first. Skip nums[i] if it equals nums[i-1] AND nums[i-1]
  // is not currently in use. This ensures duplicates are placed
  // in the same relative order, avoiding duplicate permutations.

for (int i = 0; i < nums.size(); i++) {
  if (used[i]) continue;
  if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
  used[i] = true;
  cur.push_back(nums[i]);
  backtrack(nums, used, cur, res);
  cur.pop_back();
  used[i] = false;
}

EXAMPLE — Letter Combinations of a Phone Number
https://leetcode.com/problems/letter-combinations-of-a-phone-number

Map each digit to its letters. At each step, pick one letter
for the current digit position, then move to the next digit.

void backtrack(string& digits, int idx, string& cur,
               vector<string>& res, unordered_map<char,string>& phone) {
    if (idx == digits.size()) { res.push_back(cur); return; }
    for (char c : phone[digits[idx]]) {
        cur.push_back(c);
        backtrack(digits, idx+1, cur, res, phone);
        cur.pop_back();
    }
}

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
TYPE 3 — COMBINATIONS
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

When to use:
→ Pick elements that satisfy a condition (sum = target, size = k)
→ Order does not matter
→ Elements may or may not be reused

Key difference from subsets:
Subsets collect everything.
Combinations collect only what satisfies a specific condition.

Reuse allowed → pass i (same element can appear again)
No reuse → pass i+1 (each element used at most once)

EXAMPLE — Combination Sum (elements can be reused)
https://leetcode.com/problems/combination-sum

// Sort candidates. Pass i (not i+1) to allow reuse.
// Prune: once candidates[i] > target → break (no point going further).

void backtrack(vector<int>& c, int target, int start,
               vector<int>& cur, vector<vector<int>>& res) {
    if (target == 0) { res.push_back(cur); return; }
    for (int i = start; i < c.size(); i++) {
        if (c[i] > target) break;        // pruning
        cur.push_back(c[i]);
        backtrack(c, target-c[i], i, cur, res);   // i = reuse allowed
        cur.pop_back();
    }
}

EXAMPLE — Combination Sum II (each element used once, no duplicate combos)
https://leetcode.com/problems/combination-sum-ii

// Sort. Pass i+1 (no reuse). Skip duplicates at the same level.

void backtrack(vector<int>& c, int target, int start,
               vector<int>& cur, vector<vector<int>>& res) {
    if (target == 0) { res.push_back(cur); return; }
    for (int i = start; i < c.size(); i++) {
        if (c[i] > target) break;
        if (i > start && c[i] == c[i-1]) continue;   // skip duplicate
        cur.push_back(c[i]);
        backtrack(c, target-c[i], i+1, cur, res);
        cur.pop_back();
    }
}

EXAMPLE — Generate Parentheses
https://leetcode.com/problems/generate-parentheses

// At each step, two choices: add '(' or ')'.
// Constraint: open count <= n, close count <= open count.

void backtrack(int n, int open, int close, string& cur,
               vector<string>& res) {
    if (cur.size() == 2*n) { res.push_back(cur); return; }
    if (open < n) {
        cur.push_back('(');
        backtrack(n, open+1, close, cur, res);
        cur.pop_back();
    }
    if (close < open) {
        cur.push_back(')');
        backtrack(n, open, close+1, cur, res);
        cur.pop_back();
    }
}

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
TYPE 4 — CONSTRAINT SATISFACTION
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

When to use:
→ Place elements on a board satisfying strict rules
→ "Find all valid configurations"
→ Every placement must be validated before recursing deeper

Keywords: "N-Queens", "Sudoku", "valid placement", "no two conflict"

The key: check ALL constraints BEFORE placing.
If invalid → skip. If valid → place, recurse, undo.

EXAMPLE — N-Queens
https://leetcode.com/problems/n-queens

Place one queen per row. Try every column in that row.
A placement is valid if no queen shares a column, diagonal, or anti-diagonal.
Track three sets to check conflicts in O(1).

void backtrack(int n, int row, vector<string>& board,
               vector<vector<string>>& res,
               set<int>& cols, set<int>& diag, set<int>& anti) {
    if (row == n) { res.push_back(board); return; }
    for (int col = 0; col < n; col++) {
        if (cols.count(col) || diag.count(row-col) || anti.count(row+col))
            continue;                          // conflicts → skip
        board[row][col] = 'Q';
        cols.insert(col); diag.insert(row-col); anti.insert(row+col);
        backtrack(n, row+1, board, res, cols, diag, anti);
        board[row][col] = '.';
        cols.erase(col); diag.erase(row-col); anti.erase(row+col);
    }
}

vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> res;
    vector<string> board(n, string(n, '.'));
    set<int> cols, diag, anti;
    backtrack(n, 0, board, res, cols, diag, anti);
    return res;
}

EXAMPLE — Sudoku Solver (Hard)
https://leetcode.com/problems/sudoku-solver

Find the first empty cell. Try digits 1-9.
For each digit, check row, column, and 3x3 box.
If valid → place it, recurse. If recursion fails → undo (backtrack).

bool solve(vector<vector<char>>& board) {
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            if (board[r][c] != '.') continue;
            for (char d = '1'; d <= '9'; d++) {
                if (isValid(board, r, c, d)) {
                    board[r][c] = d;
                    if (solve(board)) return true;
                    board[r][c] = '.';   // backtrack
                }
            }
            return false;   // no digit worked → tell caller to backtrack
        }
    }
    return true;   // no empty cell left → solved
}

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PRUNING — THE DIFFERENCE BETWEEN FAST AND TLE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Backtracking without pruning is brute force. Pruning cuts branches early.

  • PRUNE 1 — Check constraints BEFORE recursing, not after.
    if (choice is invalid) continue; ← prune here, before the call

  • PRUNE 2 — Sort + break when over the target.
    if (candidates[i] > target) break;
    No point checking larger values once you've already exceeded.

  • PRUNE 3 — Skip duplicates at the same recursion level.
    if (i > start && nums[i] == nums[i-1]) continue;
    Without this, identical elements at the same position
    generate identical branches → duplicate results.

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
HOW TO IDENTIFY WHICH TYPE — DECISION GUIDE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Read the problem. Ask these questions in order:

  • Does it have hard placement rules (N-Queens, Sudoku)?
    → YES → Type 4 (Constraint Satisfaction)

  • Does order matter? ([1,2] ≠ [2,1])
    → YES → Type 2 (Permutations — use visited array)

  • Does it ask for subsets satisfying a condition (sum, size)?
    → YES → Type 3 (Combinations — use start index)
    Can elements repeat? → pass i. Cannot? → pass i+1.

  • Does it ask for ALL subsets?
    → YES → Type 1 (Subsets — push at every level)

Also ask: does the input have duplicates?
→ YES → sort first, then skip duplicates in the loop.

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
COMMON MISTAKES AND HOW TO AVOID THEM
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

  • MISTAKE 1 — Forgetting to undo the choice
    This is the most common bug. If you push, you must pop.
    If you set used[i] = true, you must set it back to false.
    Without undo, every branch inherits corrupted state from the last branch.

  • MISTAKE 2 — Passing i instead of i+1 (or vice versa)
    Combination Sum (reuse ok) → pass i
    Subsets, Combos II (no reuse) → pass i+1
    Mixing these gives wrong results silently.

  • MISTAKE 3 — Not sorting before skipping duplicates
    The skip condition i > start && nums[i] == nums[i-1]
    only works correctly on sorted input.
    Always sort when the problem has duplicates.

  • MISTAKE 4 — Pushing the same result in multiple places
    For subsets → push at every level.
    For permutations/combos → push only at the base case.
    Mixing this adds wrong or duplicate entries to results.

  • MISTAKE 5 — Storing a reference instead of a copy
    res.push_back(cur) copies correctly for vector.
    If you store a pointer or reference to cur, every entry
    in res will look the same at the end (the final state of cur).

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
PRACTICE PROBLEMS — IN ORDER
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
THE BACKTRACKING CHEAT SHEET — ONE LINE EACH
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

  • All subsets → start index, push at every level
  • Subsets with duplicates → sort + skip nums[i] == nums[i-1]
  • All permutations → visited array, no start index
  • Permutations with duplicates → sort + skip if !used[i-1]
  • Combinations / target sum → start index, prune when over target
  • Reuse allowed → pass i (not i+1)
  • Constraint placement → check all rules before placing, undo after

The three steps that never change: choose → explore → unchoose.

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Drop a comment if anything is unclear.
I will write a dedicated post on any type you want.

Comments (3)