Backtracking Algorithm Fundamentals

Backtracking is essentially an exhaustive search approach optimized to avoid writing nested loops of variable depths, which becomes impractical for large datasets.

Key problem types backtracking solves:

• Combination problems: Find all valid k-element subsets from an n-element set
• Permutation problems: Determine all possible orderings of an n-element set
• Partiiton problems: Calculate valid ways to split a string/array into segments meeting conditions
• Subset problems: Enumerate all valid subsets of an n-element set
• Board problems: Solve classic puzzles like N-Queens or Sudoku

Backtracking problems can be abstracted as tree structures. The width of the tree corresponds to the size of the candidate set, while the depth corresponds to the recursion depth.

Backtracking Template

void backtrack(parameters) {
    if (termination condition) {
        store result;
        return;
    }
    for (each choice in current layer's candidate set) {
        process current node;
        backtrack(updated parameters);
        undo processing (backtrack step);
    }
}

LeetCode 77. Combinations

Problem Analysis

If solved with nested for loops, generating combinations of n elements taken k at a time would require k nested loops, which is infeasible for dynamic values of n and k.

Abstracting to a tree structure:

• Horizontal traversal: Iterate over the candidate set
• Vertical traversal: Recursively search with a narrowed candidate range to avoid duplicates

Initial Solution

class Solution {
public:
    vector<vector<int>> combine(int total, int k) {
        results.clear();
        currentPath.clear();
        backtrack(total, k, 1);
        return results;
    }

private:
    vector<vector<int>> results;
    vector<int> currentPath;
    void backtrack(int total, int k, int startIdx) {
        if (currentPath.size() == k) {
            results.push_back(currentPath);
            return;
        }
        for (int i = startIdx; i <= total; ++i) {
            currentPath.push_back(i);
            backtrack(total, k, i + 1);
            currentPath.pop_back();
        }
    }
};

Pruning Optimization

Early termination of recursion branches that cannot form valid k-element combinations reduces unnecessary calculations. The pruning condition checks if the remaining candidate elements are sufficient to complete the combination.

Optimized Solution

class Solution {
public:
    vector<vector<int>> combine(int total, int k) {
        results.clear();
        currentPath.clear();
        backtrack(total, k, 1);
        return results;
    }

private:
    vector<vector<int>> results;
    vector<int> currentPath;
    void backtrack(int total, int k, int startIdx) {
        if (currentPath.size() == k) {
            results.push_back(currentPath);
            return;
        }
        int remaining = k - currentPath.size();
        int upperBound = total - remaining + 1;
        for (int i = startIdx; i <= upperBound; ++i) {
            currentPath.push_back(i);
            backtrack(total, k, i + 1);
            currentPath.pop_back();
        }
    }
};