回溯算法小结
一、回溯算法介绍
1.1 定义1.2 特征 二、应用举例
2.1 Leetcode 46 全排列2.2 Leetcode 39 组合总和
一、回溯算法介绍 1.1 定义
回溯算法是指：用深度优先搜索对可行解进行暴力枚举，并在枚举后撤销当前操作，从而反复递归进行的搜索算法。
1.2 特征
经过总结，回溯算法主要有如下特征：
尝试【新的变化】以该【新的变化】作为新的迭代入口进行迭代撤销【新的变化】重复以上过程 二、应用举例 2.1 Leetcode 46 全排列
代码如下：
vector> permute(vector& nums) { vector> ans; backtracking(nums, ans, 0); return ans;}void backtracking(vector& nums, vector> ans, int pos) {// 递归出口（回溯法是递归，也要遵循递归的写法）if (pos = nums.size() - 1) {ans.push(nums); return ;}// 递归条件backtrcking(nums, ans, pos + 1); // 不交换顺序，它本身也是一个解for (int i = pos + 1; i < nums.size(); ++i) { // 重复以下过程swap(nums[pos], nums[i]); // 尝试【新的变化】backtracking(nums, ans, i); // 以该【新的变化】作为新的迭代入口进行迭代swap(nus[pos], nums[i); // 撤销【新的变化】}}
2.2 Leetcode 39 组合总和
代码如下：
vector> combinationSum(vector& candidates, int target) { vector> ans; vector path; backtracking(candidates, target, path, ans, 0); return ans;}void backtracking(vector& candidates, int target, vector& path, vector>& ans, int pos) {// 不需要规定退出条件，因为下面的target > candidates[i]提前做了限制for (int i = pos; i < candidates.size(); ++i) { // 重复以下过程path.push_back(candidates[i]); // 尝试【新的变化】if (target == candidates[i]) {ans.push_back(path); // 以该【新的变化】作为新的迭代入口进}else if (target > candidates[i]) {backtracking(candidates, target - candidates[i], path, ans, pos);}path.pop_back(candidates[i]); // 撤销【新的变化】}}