回溯算法：暴力枚举最优解

一、上期回顾吃透二分查找三大模板基础查找、左边界、右边界掌握二分答案解题思维有序数组最优解法全部拿下。今天正式攻克回溯算法暴力枚举最优写法解决排列、组合、子集、棋盘类所有搜索题。二、递归与回溯核心思想递归函数自身调用自身层层深入回溯走到尽头原路退回撤销当前选择尝试其他路线本质深度优先搜索 DFS暴力枚举所有合法方案适用场景枚举所有方案、路径选择、组合排列、棋盘搜索三、回溯通用万能模板void backtrack(参数) { // 1. 递归终止条件 if(满足结束条件) { 收集答案; return; } // 2. 遍历所有选择 for(选择 : 可选范围) { 剪枝排除不合法选择 做出选择 递归深入 撤销选择回溯 } }核心精髓选 → 递归 → 撤销四、经典题型 1子集问题从数组中选出所有不重复子集#include iostream #include vector using namespace std; vectorvectorint res; vectorint path; void subsets(vectorint nums, int start) { // 每次进入都收集结果 res.push_back(path); for(int i start; i nums.size(); i) { path.push_back(nums[i]); subsets(nums, i 1); path.pop_back(); // 回溯 } } int main() { vectorint nums {1,2,3}; subsets(nums, 0); for(auto v : res) { for(int x : v) cout x ; cout endl; } return 0; }五、经典题型 2组合问题从 n 个数中选 k 个数组合vectorvectorint res; vectorint path; void combine(int n, int k, int start) { // 终止路径长度等于k if(path.size() k) { res.push_back(path); return; } for(int i start; i n; i) { path.push_back(i); combine(n, k, i 1); path.pop_back(); } }六、经典题型 3全排列数组元素全排列无重复元素vectorvectorint res; vectorint path; bool used[10] {false}; void permute(vectorint nums) { 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]); permute(nums); path.pop_back(); used[i] false; // 回溯撤销 } }七、去重核心技巧数组有重复元素避免重复方案先排序数组同层跳过相同元素if(i start nums[i] nums[i-1]) continue;八、回溯剪枝优化提前排除不可能答案大幅减少递归次数例组合求和超出目标值直接 return不再向下递归九、回溯三大区别牢记子集start 从当前下一位不限长度全部收集组合start 向后走不回头固定选取个数排列start 从头遍历使用 used 数组标记已选元素十、今日核心总结回溯 递归深度搜索 状态撤销固定流程终止条件 → 遍历选择 → 递归 → 回溯start 下标控制顺序避免组合重复used 数组标记元素实现全排列排序 同层去重解决重复数组问题剪枝是提升回溯效率关键十一、课后练习手写子集回溯代码输出所有结果实现从 1~5 中选 3 个数组合独立写出无重复数组全排列