Backtracking Algorithm

Understanding Backtracking

Backtracking solves problems by exploring all possible solutions in a systematic way, often represented as a tree structure. The algorithm recursively searches through subsets, where the size of the original set determines the tree's width, and the recursion depth determines its height. Since recursion requires termination codnitions, the resulting tree is finite (an N-ary tree).

In essence, backtracking is a brute-force search method that uses recursion to control nested loops.

Backtracking Template

• Function Return Type and Parameters

Backtracking functions typically return void. The parameters are determined based on the specific problem requirements, often added during implementation ratheer than predefined.

void backtrack(parameters)

• Termination Condition

Every backtracking problem needs a termination condition to stop recursion when a valid solution is found (i.e., reaching a leaf node in the tree).

if (termination condition) {
    store result;
    return;
}

• Search Process

The algorithm explores the tree by iterating through choices at each level (horizontal traversal) and recursively exploring deeper levels (vertical traversal).

for (choice: elements in current level) {
    process node;
    backtrack(path, choices); // recursion
    undo processing; // backtrack
}

Complete Backtracking Framework

void backtrack(parameters) {
    if (termination condition) {
        store result;
        return;
    }

    for (choice: elements in current level) {
        process node;
        backtrack(path, choices);
        undo processing;
    }
}

77. Combinations

LeetCode Problem Link

Article Explanation: 77. Combinations

Video Explanation: Mastering Backtracking - Combination Problem (LeetCode 77) with Pruning

Status: Need to visualize combinations as tree structures

Tree Structure

Problems must be abstracted into tree structures. For combinations, we can visualize the search process as follows:

Each combination only includes subsequent numbers to avoid duplicates.

Backtracking Three Steps

1. Recursion Function Parameters and Return Value
   • Return type is usually void
   • Use a vector to store the current path (currentCombination)
   • Use another vector to store all valid combinations (combinations)
   • Include start to track the beginning of the search range

void backtrack(int n, int k, int start)

2. Termination Condition
   • When the current combination reaches size k, store it and return

if (currentCombination.size() == k) {
    combinations.push_back(currentCombination);
    return;
}

3. Single-Level Logic
   • Iterate through remaining elements starting from start

for (int i = start; i <= n; i++) {
    currentCombination.push_back(i);
    backtrack(n, k, i + 1);
    currentCombination.pop_back();
}

C++ Implementation

#include <vector>
using namespace std;

class Solution {
private:
    vector<vector<int>> combinations;
    vector<int> currentCombination;
    
    void backtrack(int n, int k, int start) {
        if (currentCombination.size() == k) {
            combinations.push_back(currentCombination);
            return;
        }
        
        for (int i = start; i <= n; i++) {
            currentCombination.push_back(i);
            backtrack(n, k, i + 1);
            currentCombination.pop_back();
        }
    }

public:
    vector<vector<int>> combine(int n, int k) {
        combinations.clear();
        currentCombination.clear();
        backtrack(n, k, 1);
        return combinations;
    }
};

Pruning for Combination Problems

Pruning optimizes the search by eliminating unnecessary branches when the remaining elements cannot satisfy the requirements.

For the combination problem, we focus on the for loop's starting position:

for (int i = start; i <= n; i++) {

Optimization logic:

1. Already selected elements: currentCombination.size()
2. Still needed: k - currentCombination.size()
3. Remaining elements: n - i
4. Pruning condition: n - i >= k - currentCombination.size()
5. Adjusted loop range: i <= n - (k - currentCombination.size()) + 1

Why +1? This accounts for inclusive range boundaries.

Example: n = 4, k = 3, selected = 0 elements

• n - (k - 0) + 1 = 4 - 3 + 1 = 2
• Valid combinations start from 2: [2,3,4]

Optimized loop:

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