Fundamentals of Backtracking

Backtracking is essentially a systematic form of brute-force search. It operates on the principle of exploring potential solutions by abandoning paths that fail to satisfy the constraints of the problem as early as possible. This technique is a natural byproduct of recursion; whenever recursion is used to explore a decision tree, the process of returning from a recursive call to explore alternative branches is known as backtracking.

Algorithmic Efficiency

While backtracking is a powerful method for solving complex problems, it is not inherently efficient. Its core nature is exhaustive search. Optimization via "pruning"—cutting off branches of the search tree that cannot possibly lead to a valid solution—can improve performance, but it does not change the fundamental fact that, in the worst case, it examines all possibilities. We use it because, for many problems like NP-complete ones, no known polynomial-time solution exists, making a smart brute-force search the best approach.

Problem Categories

Backtracking is typically used to solve problems involving:

• Combinations: Finding k elements from a set of N that satisfy specific rules.
• Cutting/Partitioning: Splitting a string according to specific rules.
• Subsets: Finding all subsets of a set that meet certain conditions.
• Permutations: Arranging N numbers in specific orders.
• Chessboard/Constraint Satisfaction: N-Queens, Sudoku, etc.

Tree Abstraction

A key mental model for backtracking is visualizing the search space as an N-ary tree. The width of the tree represents the number of choices available at each step (the size of the set), and the depth represents the number of recursive steps. The goal is to traverse this tree, usually aiming for the leaf nodes which represent complete solutions.

Standard Template

The structure of a backtracking algorithm generally follows three steps:

1. Return Value and Parameters: The function usually returns void. Parameters define the current state (path, start index, etc.).
2. Termination Condition: When a valid solution is found (often reaching a leaf node), record the result and return.
3. Search Process: Iterate through available choices (for loop), process the node, recurse, and then backtrack (undo the processing).

void explore(parameters) {
    if (termination_condition) {
        store_result;
        return;
    }
    for (choice : available_choices) {
        process_node(choice);
        explore(next_parameters);
        backtrack_node(choice);
    }
}

---

Combinations

Problem 1: Basic Combinations

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].

While nested loops work for fixed k, the depth of recursion makes backtracking ideal for variable k. The logic involves starting from a specific index to avoid duplicate combinations and ensure order.

class Solution {
private:
    vector solutions;
    vector<int> current;
    void dfs(int n, int k, int startIdx) {
        if (current.size() == k) {
            solutions.push_back(current);
            return;
        }
        // Pruning: Limit the loop to remaining elements needed
        for (int i = startIdx; i <= n - (k - current.size()) + 1; ++i) {
            current.push_back(i);
            dfs(n, k, i + 1);
            current.pop_back(); // Backtrack
        }
    }
public:
    vector combine(int n, int k) {
        dfs(n, k, 1);
        return solutions;
    }
};

Problem 2: Combination Sum III

Find all valid combinations of k numbers that sum to n, using only numbers from 1 to 9. Each number is used at most once.

This adds a constraint on the sum of elements. We add a `currentSum` parameter to track the total.

class Solution {
private:
    vector results;
    vector<int> path;
    void backtrack(int target, int k, int currentSum, int startIdx) {
        if (path.size() == k) {
            if (currentSum == target) results.push_back(path);
            return;
        }
        for (int i = startIdx; i <= 9; ++i) {
            int sum = currentSum + i;
            if (sum > target) break; // Prune if sum exceeds target
            path.push_back(i);
            backtrack(target, k, sum, i + 1);
            path.pop_back();
        }
    }
public:
    vector combinationSum3(int k, int n) {
        backtrack(n, k, 0, 1);
        return results;
    }
};

Problem 3: Letter Combinations of a Phone Number

Given a string containing digits from 2-9, return all possible letter combinations that the number could represent.

This involves mapping digits to sets of letters. The depth of the tree equals the length of the input string. Note that this is a combination of different sets (one set per digit), unlike selecting from a single set.

class Solution {
private:
    const string digitMap[10] = {
        "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
    };
    vector<string> output;
    string currentSeq;
    void generate(const string& digits, int index) {
        if (index == digits.size()) {
            output.push_back(currentSeq);
            return;
        }
        int digit = digits[index] - '0';
        string letters = digitMap[digit];
        for (char c : letters) {
            currentSeq.push_back(c);
            generate(digits, index + 1);
            currentSeq.pop_back();
        }
    }
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return output;
        generate(digits, 0);
        return output;
    }
};

Problem 4: Combination Sum

Find all unique combinations in candidates where the candidate numbers sum to target. The same number may be chosen from candidates an unlimited number of times.

Key difference: The recursion for the next step starts at `i` instead of `i + 1` because reuse is allowed.

class Solution {
private:
    vector ans;
    vector<int> curr;
    void dfs(vector<int>& candidates, int target, int sum, int startIdx) {
        if (sum == target) {
            ans.push_back(curr);
            return;
        }
        for (int i = startIdx; i < candidates.size(); ++i) {
            if (sum + candidates[i] > target) break;
            curr.push_back(candidates[i]);
            dfs(candidates, target, sum + candidates[i], i); // Reuse allowed: use i
            curr.pop_back();
        }
    }
public:
    vector combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        dfs(candidates, target, 0, 0);
        return ans;
    }
};

Problem 5: Combination Sum II

Similar to the previous problem, but each number in candidates may only be used once in the combination. The solution set must not contain duplicate combinations.

This requires sorting the array and using a `used` array (or checking index) to skip duplicates at the same tree level.

class Solution {
private:
    vector res;
    vector<int> comb;
    void findCombinations(vector<int>& candidates, int target, int sum, int startIdx, vector<bool>& used) {
        if (sum == target) {
            res.push_back(comb);
            return;
        }
        for (int i = startIdx; i < candidates.size(); ++i) {
            if (sum + candidates[i] > target) break;
            // Skip duplicates at the same level
            if (i > 0 && candidates[i] == candidates[i-1] && !used[i-1]) continue;
            
            used[i] = true;
            comb.push_back(candidates[i]);
            findCombinations(candidates, target, sum + candidates[i], i + 1, used);
            comb.pop_back();
            used[i] = false;
        }
    }
public:
    vector combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<bool> used(candidates.size(), false);
        findCombinations(candidates, target, 0, 0, used);
        return res;
    }
};

---

Partitioning Problems

Problem 6: Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning.

Partitioning is analogous to cutting a string. The tree abstraction involves making cuts at different indices. We must verify if a substring is a palindrome before recursing.

class Solution {
private:
    vector result;
    vector<string> path;
    bool isPalindrome(const string& s, int l, int r) {
        while (l < r) {
            if (s[l] != s[r]) return false;
            l++; r--;
        }
        return true;
    }
    void backtracking(const string& s, int startIdx) {
        if (startIdx >= s.size()) {
            result.push_back(path);
            return;
        }
        for (int i = startIdx; i < s.size(); ++i) {
            if (isPalindrome(s, startIdx, i)) {
                string sub = s.substr(startIdx, i - startIdx + 1);
                path.push_back(sub);
                backtracking(s, i + 1);
                path.pop_back();
            }
        }
    }
public:
    vector partition(string s) {
        backtracking(s, 0);
        return result;
    }
};

Problem 7: Restore IP Addresses

A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros. Given a string s containing only digits, return all possible valid IP addresses.

This is a specific partitioning problem with constraints: exactly 3 dots (4 segments), valid range, and no leading zeros.

class Solution {
private:
    vector<string> res;
    bool isValid(const string& s, int start, int end) {
        if (start > end) return false;
        if (s[start] == '0' && start != end) return false;
        int num = 0;
        for (int i = start; i <= end; ++i) {
            if (!isdigit(s[i])) return false;
            num = num * 10 + (s[i] - '0');
            if (num > 255) return false;
        }
        return true;
    }
    void backtrack(string& s, int startIdx, int dotNum) {
        if (dotNum == 3) {
            if (isValid(s, startIdx, s.size() - 1)) res.push_back(s);
            return;
        }
        for (int i = startIdx; i < s.size(); ++i) {
            if (isValid(s, startIdx, i)) {
                s.insert(s.begin() + i + 1, '.');
                backtrack(s, i + 2, dotNum + 1);
                s.erase(s.begin() + i + 1);
            } else break;
        }
    }
public:
    vector<string> restoreIpAddresses(string s) {
        backtrack(s, 0, 0);
        return res;
    }
};

---

Subsets

Problem 8: Subsets

Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets.

Unlike combination problems where we collect results only at leaf nodes, for subsets, we collect results at every node of the tree.

class Solution {
private:
    vector output;
    vector<int> curr;
    void traverse(vector<int>& nums, int startIdx) {
        output.push_back(curr);
        for (int i = startIdx; i < nums.size(); ++i) {
            curr.push_back(nums[i]);
            traverse(nums, i + 1);
            curr.pop_back();
        }
    }
public:
    vector subsets(vector<int>& nums) {
        traverse(nums, 0);
        return output;
    }
};

Problem 9: Subsets II

Given an integer array nums that may contain duplicates, return all possible subsets. The solution set must not contain duplicate subsets.

Similar to Combination Sum II, we sort the array and skip duplicates at the same level of the tree.

class Solution {
private:
    vector res;
    vector<int> path;
    void solve(vector<int>& nums, int startIdx) {
        res.push_back(path);
        for (int i = startIdx; i < nums.size(); ++i) {
            if (i > startIdx && nums[i] == nums[i-1]) continue;
            path.push_back(nums[i]);
            solve(nums, i + 1);
            path.pop_back();
        }
    }
public:
    vector subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        solve(nums, 0);
        return res;
    }
};

---

Permutations

Problem 10: Permutations

Given an array nums of distinct integers, return all the possible permutations.

Unlike combinations, order matters in permutations (e.g., [1,2] and [2,1] are different). We maintain a `used` array to track which elements are currently in the path. The loop always starts from 0.

class Solution {
private:
    vector result;
    vector<int> curr;
    void permute(vector<int>& nums, vector<bool>& visited) {
        if (curr.size() == nums.size()) {
            result.push_back(curr);
            return;
        }
        for (int i = 0; i < nums.size(); ++i) {
            if (visited[i]) continue;
            visited[i] = true;
            curr.push_back(nums[i]);
            permute(nums, visited);
            curr.pop_back();
            visited[i] = false;
        }
    }
public:
    vector permute(vector<int>& nums) {
        vector<bool> visited(nums.size(), false);
        permute(nums, visited);
        return result;
    }
};

Problem 11: Permutations II

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations.

We sort `nums` and use a `visited` array. The condition `if (i > 0 && nums[i] == nums[i-1] && !visited[i-1]) continue` ensures we skip used duplicates at the same tree level.

class Solution {
private:
    vector ans;
    vector<int> path;
    void backtrack(vector<int>& nums, vector<bool>& used) {
        if (path.size() == nums.size()) {
            ans.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); ++i) {
            if (used[i]) continue;
            // Skip duplicates used at this level
            if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
            
            used[i] = true;
            path.push_back(nums[i]);
            backtrack(nums, used);
            path.pop_back();
            used[i] = false;
        }
    }
public:
    vector permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<bool> used(nums.size(), false);
        backtrack(nums, used);
        return ans;
    }
};

---

Advanced Problems

Problem 12: Reconstruct Itinerary

You are given a list of airline tickets where tickets[i] = [from_i, to_i] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.

This problem is essentially finding an Eulerian path in a directed graph. We can use backtracking with a map structure to handle lexicographical ordering and ticket usage.

class Solution {
private:
    unordered_map> graph;
    bool dfs(int ticketNum, vector<string>& route) {
        if (route.size() == ticketNum + 1) return true;
        
        string current = route.back();
        for (auto& dest : graph[current]) {
            if (dest.second > 0) { // If tickets are available
                route.push_back(dest.first);
                dest.second--; // Use ticket
                if (dfs(ticketNum, route)) return true;
                route.pop_back();
                dest.second++; // Restore ticket
            }
        }
        return false;
    }
public:
    vector<string> findItinerary(vector& tickets) {
        for (auto& t : tickets) {
            graph[t[0]][t[1]]++; // Build graph and count tickets
        }
        vector<string> route;
        route.push_back("JFK"); // Start from JFK
        dfs(tickets.size(), route);
        return route;
    }
};

Problem 13: N-Queens

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

We treat the chessboard as a matrix. The depth of the tree is the row index. For each row, we iterate through columns to find a valid spot for the queen, checking columns and diagonals.

class Solution {
private:
    vector boards;
    bool isValid(int row, int col, vector<string>& board, int n) {
        for (int i = 0; i < row; ++i) {
            if (board[i][col] == 'Q') return false;
        }
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {
            if (board[i][j] == 'Q') return false;
        }
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j) {
            if (board[i][j] == 'Q') return false;
        }
        return true;
    }
    void solve(int n, int row, vector<string>& board) {
        if (row == n) {
            boards.push_back(board);
            return;
        }
        for (int col = 0; col < n; ++col) {
            if (isValid(row, col, board, n)) {
                board[row][col] = 'Q';
                solve(n, row + 1, board);
                board[row][col] = '.';
            }
        }
    }
public:
    vector solveNQueens(int n) {
        vector<string> board(n, string(n, '.'));
        solve(n, 0, board);
        return boards;
    }
};

Problem 14: Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.

Sudoku solving is a two-dimensional backtracking problem. We iterate through every cell. If a cell is empty, we try digits 1-9. If valid, we place it and recurse. If the recursion returns true, we propagate true upwards.

class Solution {
private:
    bool isValid(vector& board, int row, int col, char c) {
        for (int i = 0; i < 9; ++i) {
            if (board[i][col] == c) return false;
            if (board[row][i] == c) return false;
            if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false;
        }
        return true;
    }
    bool solve(vector& board) {
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[0].size(); ++j) {
                if (board[i][j] == '.') {
                    for (char c = '1'; c <= '9'; ++c) {
                        if (isValid(board, i, j, c)) {
                            board[i][j] = c;
                            if (solve(board)) return true;
                            board[i][j] = '.';
                        }
                    }
                    return false; // No number works
                }
            }
        }
        return true; // All cells filled
    }
public:
    void solveSudoku(vector& board) {
        solve(board);
    }
};