[leetcode刷题算法总结] 回溯算法

下面给出一个常用的「回溯算法」C++ 代码示例，以及简要讲解

1. 回溯算法通用代码模板 (C++)

通常，我们会把最终结果保存在一个全局或外部变量（这里用 vector<vector<int>> result; 表示）。
然后定义一个函数 void backtrack(…){…}，其中包含「做选择 → 递归 → 撤销选择」的流程。

示例代码框架如下：

#include <bits/stdc++.h>
using namespace std;

// 全局或类内成员变量，用于存储结果
vector<vector<int>> result;

void backtrack(vector<int>& path, /* 其他参数 */) {
    // 1. 判断是否满足收集/终止条件, 有时候是不需要的比如解算子集，直接就push_back 进去
    // if (满足条件) {
    //     result.push_back(path);
    //     return;
    // }

    // 2. 遍历所有可能的选择
    // for (...) {
    //     // 做选择
    //     path.push_back(...);
    //     // 递归
    //     backtrack(path, ...);
    //     // 撤销选择
    //     path.pop_back();
    // }
}

int main(){
    // 初始化、读入数据等
    // 调用 backtrack(...) 
    // 输出/使用 result
    return 0;
}

下面，我们结合几道常见的回溯题目演示完整写法。

2. 子集 (Subsets)

题意：给定一个不含重复元素的整数数组 nums，返回它的所有子集。

思路：

1. 利用回溯深度优先搜索所有可能的组合。
2. 因为所有的时刻，当前构造的路径 path 都可以作为一个子集，所以可以在每一层搜索之前就把当前 path 记录到 result 中。
3. start 用于控制下一层从哪里开始选数，避免重复与混乱。

C++实现：

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<vector<int>> res;

    void backtrack(vector<int>& nums, int start, vector<int>& path) {
        // 收集当前子集
        res.push_back(path);

        // 从 start 开始，尝试加入后续的元素
        for(int i = start; i < (int)nums.size(); i++){
            // 做选择
            path.push_back(nums[i]);
            // 递归
            backtrack(nums, i + 1, path);
            // 撤销选择
            path.pop_back(); // 不常用，但是有这个api
        }
    }

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

int main(){
    // 示例：nums = [1,2,3]
    vector<int> nums = {1,2,3};
    Solution sol;
    auto ans = sol.subsets(nums);

    // 输出结果
    for(auto &subset : ans){
        cout << "[ ";
        for(int x : subset) cout << x << " ";
        cout << "]\n";
    }
    return 0;
}

3. 全排列 (Permutations)

题意：给定一个互不相同的整数数组 nums，返回它的所有全排列。

思路：

1. 回溯时，用一个 used 数组标记某个元素是否已经被选中。
2. 当 path 大小与 nums.size() 相等，说明已经选满了所有元素，得到一个全排列。

C++实现：

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<vector<int>> res;

    void backtrack(vector<int>& nums, vector<int>& path, vector<bool>& used) {
        // 如果已经选满
        if ((int)path.size() == (int)nums.size()) {
            res.push_back(path);
            return;
        }

        for (int i = 0; i < (int)nums.size(); i++) {
            // 如果已经使用过，跳过
            if (used[i]) continue;

            // 做选择
            path.push_back(nums[i]);
            used[i] = true;
            // 递归
            backtrack(nums, path, used);
            // 撤销选择
            path.pop_back();
            used[i] = false;
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> path;
        vector<bool> used(nums.size(), false);
        backtrack(nums, path, used);
        return res;
    }
};

int main(){
    // 示例：nums = [1,2,3]
    vector<int> nums = {1,2,3};
    Solution sol;
    auto ans = sol.permute(nums);

    // 输出结果
    for(auto &perm : ans){
        cout << "[ ";
        for(int x : perm) cout << x << " ";
        cout << "]\n";
    }
    return 0;
}

4. 组合总和 (Combination Sum)

题意：给定一个无重复元素的正整数数组 candidates 和一个目标数 target，找出所有可以使数字和为 target 的组合。数组中的同一个数字可以无限制被选取。

思路：

1. 用回溯枚举所有可能的组合。
2. 若当前和 sum 超过 target，则可以终止搜索（剪枝）。
3. 因为同一个数字可以被重复使用，所以在下一层递归时，start 不变。若不允许重复使用同一个数字，则传 start + 1 即可。

C++实现：

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<vector<int>> res;

    void backtrack(vector<int>& candidates, int start, int target, vector<int>& path, int sum) {
        // 如果达到目标
        if (sum == target) {
            res.push_back(path);
            return;
        }
        // 如果超过目标，剪枝
        if (sum > target) {
            return;
        }

        // 从 start 开始，避免重复组合
        for(int i = start; i < (int)candidates.size(); i++){
            // 做选择
            path.push_back(candidates[i]);
            // 递归，允许重复使用，所以下一层传 i 而不是 i+1
            backtrack(candidates, i, target, path, sum + candidates[i]);
            // 撤销选择
            path.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> path;
        backtrack(candidates, 0, target, path, 0);
        return res;
    }
};

int main(){
    // 示例：candidates = [2,3,6,7], target = 7
    vector<int> candidates = {2,3,6,7};
    int target = 7;
    Solution sol;
    auto ans = sol.combinationSum(candidates, target);

    // 输出结果
    for(auto &comb : ans){
        cout << "[ ";
        for(int x : comb) cout << x << " ";
        cout << "]\n";
    }
    return 0;
}

5. 小结

• 回溯算法的核心框架：
  1. 做选择：将某元素加入路径 path。
  2. 递归：进入下一层处理。
  3. 撤销选择：将刚才加入的元素移除，回到原状态。
• 通过在回溯前后加一些条件判断 (例如当前累加和、下标范围、是否被使用等)，可以灵活处理各种组合、排列、子集、分割问题。
• 在 C++ 中，如果需要存储当前路径到 result，常用 path 的拷贝 res.push_back(path);，注意回溯结束要将状态复原。