回溯算法核心：子集、组合、排列全解析

一、回溯核心思想

回溯 = 深度优先搜索 + 状态撤销

1. 逐个选择元素，向下递归探索路径
2. 满足条件记录结果
3. 回溯撤销上一步选择，尝试其他分支本质：穷举所有合法方案，剪枝剔除无效路径

二、回溯算法四要素

1. 路径：当前已选择的元素集合
2. 选择列表：当前可选取的元素
3. 终止条件：路径满足要求，保存答案
4. 回溯撤销：递归返回后恢复状态

三、通用标准模板

vector<vector<int>> res; vector<int> path; void backtrack(参数) { // 1. 终止条件，收集结果 if(满足条件) { res.push_back(path); return; } // 2. 遍历所有可选元素 for(遍历范围) { // 剪枝：跳过不符合条件选项 if(不符合规则) continue; // 3. 做出选择 path.push_back(当前元素); // 4. 递归深入 backtrack(更新参数); // 5. 撤销选择，回溯 path.pop_back(); } }

四、题型 1：子集问题

无重复数组，输出所有子集

vector<vector<int>> subsets(vector<int>& nums) { res.clear(); path.clear(); backSub(nums, 0); return res; } void backSub(vector<int>& nums, int start) { res.push_back(path); for(int i = start; i < nums.size(); i++) { path.push_back(nums[i]); backSub(nums, i+1); path.pop_back(); } }

要点：start 控制起始位置，避免重复子集

五、题型 2：组合问题

从数组选 k 个数组合，和为目标值

vector<vector<int>> combine(int n, int k) { res.clear(); path.clear(); backCom(n, k, 1); return res; } void backCom(int n, int k, int start) { if(path.size() == k) { res.push_back(path); return; } for(int i = start; i <= n; i++) { path.push_back(i); backCom(n, k, i+1); path.pop_back(); } }

六、题型 3：排列问题

数组元素全排列，顺序不同视为不同方案

vector<vector<int>> permute(vector<int>& nums) { res.clear(); path.clear(); vector<bool> used(nums.size(), false); backPer(nums, used); return res; } void backPer(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]); backPer(nums, used); path.pop_back(); used[i] = false; } }

要点：used 数组标记元素是否已选用

七、三类题型核心区别

1. 子集：start 向后推进，元素不回头选，数量不限
2. 组合：固定元素个数，同子集不调换顺序
3. 排列：可回头选取未用元素，顺序不同算新解

八、回溯常见剪枝场景

1. 求和类：当前和超出目标直接终止分支
2. 重复元素：跳过相同值避免重复答案
3. 范围超限：下标越界立刻停止递归

九、高频适用题型

1. 子集、组合、全排列
2. 电话号码字母组合
3. N 皇后、数独求解
4. 分割回文串
5. 所有可行路径搜索

十、新手易错点

1. 忘记 pop_back 撤销状态，路径数据错乱
2. start 下标控制错误，生成重复结果
3. 排列未做使用标记，元素重复选取
4. 终止条件判断失误，结果收集不全

十一、今日总结

1. 回溯核心：选元素→递归探索→回溯撤销
2. 一套通用模板适配子集、组合、排列三大题型
3. start 下标、used 标记是区分题型关键
4. 合理剪枝可以大幅降低算法耗时