前言
回溯算法是基于**深度优先搜索（DFS）**的经典算法思想，核心是“尝试-回退”，通过遍历解空间找到所有符合条件的解。它广泛应用于排列、组合、子集等问题，本文将结合LeetCode经典例题，用C++实现回溯算法，讲解核心思路与实战技巧。
一、回溯算法通用框架（C++）
回溯的核心是递归函数中完成选择-递归-撤销选择的循环，C++通用框架模板如下：
cpp
#include <vector>
using namespace std;
vector<vector<int>> result; // 存储最终结果
void backtrack(/* 路径，选择列表，其他参数 */) {
if (/* 结束条件 */) {
result.push_back(/* 当前路径 */);
return;
}
for (/* 遍历选择列表 */) {
// 做选择
// 递归
backtrack(/* 新的路径和选择列表 */);
// 撤销选择
}
}
二、经典例题C++实现
2.1 组合问题（LeetCode 77. 组合）
题目：给定 n 和 k ，返回 [1,n] 中所有 k 个数的组合。
思路：用 start 控制选择起点避免重复，路径长度等于 k 时保存结果，同时剪枝优化。
cpp
#include <vector>
using namespace std;
class Solution {
private:
vector<vector<int>> res;
vector<int> path;
void backtrack(int n, int k, int start) {
if (path.size() == k) {
res.push_back(path);
return;
}
// 剪枝：剩余数字不足时直接退出
for (int i = start; i <= n - (k - path.size()) + 1; ++i) {
path.push_back(i); // 做选择
backtrack(n, k, i + 1); // 递归
path.pop_back(); // 撤销选择
}
}
public:
vector<vector<int>> combine(int n, int k) {
backtrack(n, k, 1);
return res;
}
};
2.2 全排列问题（LeetCode 46. 全排列）
题目：给定无重复数字的数组 nums ，返回所有全排列。
思路：用 used 数组标记已选元素，路径长度等于数组长度时保存结果。
cpp
#include <vector>
using namespace std;
class Solution {
private:
vector<vector<int>> res;
vector<int> path;
void backtrack(vector<int>& nums, vector<bool>& used) {
if (path.size() == nums.size()) {
res.push_back(path);
return;
}
for (int i = 0; i < nums.size(); ++i) {
if (used[i]) continue; // 跳过已选元素
used[i] = true; // 做选择
path.push_back(nums[i]);
backtrack(nums, used); // 递归
path.pop_back(); // 撤销选择
used[i] = false;
}
}
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<bool> used(nums.size(), false);
backtrack(nums, used);
return res;
}
};
2.3 子集问题（LeetCode 78. 子集）
题目：给定数组 nums ，返回所有可能的子集（幂集）。
思路：遍历过程中每一步的路径都是一个子集，直接保存，用 start 控制选择起点避免重复。
cpp
#include <vector>
using namespace std;
class Solution {
private:
vector<vector<int>> res;
vector<int> path;
void backtrack(vector<int>& nums, int start) {
res.push_back(path); // 每一步都保存子集
for (int i = start; i < nums.size(); ++i) {
path.push_back(nums[i]); // 做选择
backtrack(nums, i + 1); // 递归
path.pop_back(); // 撤销选择
}
}
public:
vector<vector<int>> subsets(vector<int>& nums) {
backtrack(nums, 0);
return res;
}
};
三、回溯算法优化技巧
1. 剪枝：提前判断当前路径是否无法得到有效解，直接跳过分支（如组合问题中 i <= n - (k - path.size()) + 1 ）。
2. 状态标记：用 bool 数组/哈希表标记已使用元素，避免重复选择（如全排列的 used 数组）。
3. 排序去重：若数组含重复元素（如LeetCode 47. 全排列 II），先排序再跳过重复元素，避免生成重复解。
四、应用场景
回溯算法适用于需要穷举所有可能解的场景：
- 排列/组合/子集类问题；
- N皇后、数独等棋盘问题；
- 单词搜索、迷宫路径等搜索问题；
- 分割回文串、复原IP地址等分割问题。
