一、回溯核心思想回溯 深度优先搜索 状态撤销逐个选择元素向下递归探索路径满足条件记录结果回溯撤销上一步选择尝试其他分支本质穷举所有合法方案剪枝剔除无效路径二、回溯算法四要素路径当前已选择的元素集合选择列表当前可选取的元素终止条件路径满足要求保存答案回溯撤销递归返回后恢复状态三、通用标准模板vectorvectorint res; vectorint 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子集问题无重复数组输出所有子集vectorvectorint subsets(vectorint nums) { res.clear(); path.clear(); backSub(nums, 0); return res; } void backSub(vectorint nums, int start) { res.push_back(path); for(int i start; i nums.size(); i) { path.push_back(nums[i]); backSub(nums, i1); path.pop_back(); } }要点start 控制起始位置避免重复子集五、题型 2组合问题从数组选 k 个数组合和为目标值vectorvectorint 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, i1); path.pop_back(); } }六、题型 3排列问题数组元素全排列顺序不同视为不同方案vectorvectorint permute(vectorint nums) { res.clear(); path.clear(); vectorbool used(nums.size(), false); backPer(nums, used); return res; } void backPer(vectorint nums, vectorbool 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 数组标记元素是否已选用七、三类题型核心区别子集start 向后推进元素不回头选数量不限组合固定元素个数同子集不调换顺序排列可回头选取未用元素顺序不同算新解八、回溯常见剪枝场景求和类当前和超出目标直接终止分支重复元素跳过相同值避免重复答案范围超限下标越界立刻停止递归九、高频适用题型子集、组合、全排列电话号码字母组合N 皇后、数独求解分割回文串所有可行路径搜索十、新手易错点忘记 pop_back 撤销状态路径数据错乱start 下标控制错误生成重复结果排列未做使用标记元素重复选取终止条件判断失误结果收集不全十一、今日总结回溯核心选元素→递归探索→回溯撤销一套通用模板适配子集、组合、排列三大题型start 下标、used 标记是区分题型关键合理剪枝可以大幅降低算法耗时
