网站黑链怎么做的,公司部门管理制度,免费网站安全软件下载安装,衡阳做网站优化回溯法模板
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择#xff1a;本层集合中元素#xff08;树中节点孩子的数量就是集合的大小#xff09;) {处理节点;backtracking(路径#xff0c;选择列表); // 递归回溯#xff0c;撤销处理结果}
}理解 从…回溯法模板
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果}
}理解 从图中看出for循环可以理解是横向遍历backtracking递归就是纵向遍历这样就把这棵树全遍历完了一般来说搜索叶子节点就是找的其中一个结果了
回溯法解决的问题都可以抽象为树形结构N叉树用树形结构来理解回溯就容易多了
第77题. 组合 理解 回溯代码
class Solution {
private:vectorvectorint result; // 存放符合条件结果的集合vectorint path; // 用来存放符合条件结果void backtracking(int n, int k, int startIndex) {if (path.size() k) {result.push_back(path);return;}for (int i startIndex; i n; i) {path.push_back(i); // 处理节点 backtracking(n, k, i 1); // 递归path.pop_back(); // 回溯撤销处理的节点}}
public:vectorvectorint combine(int n, int k) {result.clear(); // 可以不写path.clear(); // 可以不写backtracking(n, k, 1);return result;}
};剪枝操作
class Solution {
private:vectorvectorint result;vectorint path;void backtracking(int n, int k, int startIndex) {if (path.size() k) {result.push_back(path);return;}for (int i startIndex; i n - (k - path.size()) 1; i) { // 优化的地方path.push_back(i); // 处理节点backtracking(n, k, i 1);path.pop_back(); // 回溯撤销处理的节点}}
public:vectorvectorint combine(int n, int k) {backtracking(n, k, 1);return result;}
};
216.组合总和III 思路 回溯算法
class Solution {
private:vectorvectorint result; // 存放结果集vectorint path; // 符合条件的结果// targetSum目标和也就是题目中的n。// k题目中要求k个数的集合。// sum已经收集的元素的总和也就是path里元素的总和。// startIndex下一层for循环搜索的起始位置。void backtracking(int targetSum, int k, int sum, int startIndex) {if (path.size() k) {if (sum targetSum) result.push_back(path);return; // 如果path.size() k 但sum ! targetSum 直接返回}for (int i startIndex; i 9; i) {sum i; // 处理path.push_back(i); // 处理backtracking(targetSum, k, sum, i 1); // 注意i1调整startIndexsum - i; // 回溯path.pop_back(); // 回溯}}public:vectorvectorint combinationSum3(int k, int n) {result.clear(); // 可以不加path.clear(); // 可以不加backtracking(n, k, 0, 1);return result;}
};
剪枝操作
class Solution {
private:vectorvectorint result; // 存放结果集vectorint path; // 符合条件的结果void backtracking(int targetSum, int k, int sum, int startIndex) {if (sum targetSum) { // 剪枝操作return; // 如果path.size() k 但sum ! targetSum 直接返回}if (path.size() k) {if (sum targetSum) result.push_back(path);return;}for (int i startIndex; i 9 - (k - path.size()) 1; i) { // 剪枝sum i; // 处理path.push_back(i); // 处理backtracking(targetSum, k, sum, i 1); // 注意i1调整startIndexsum - i; // 回溯path.pop_back(); // 回溯}}public:vectorvectorint combinationSum3(int k, int n) {result.clear(); // 可以不加path.clear(); // 可以不加backtracking(n, k, 0, 1);return result;}
};
17.电话号码的字母组合 39. 组合总和 思路 回溯法代码
// 版本一
class Solution {
private:const string letterMap[10] {, // 0, // 1abc, // 2def, // 3ghi, // 4jkl, // 5mno, // 6pqrs, // 7tuv, // 8wxyz, // 9};
public:vectorstring result;string s;void backtracking(const string digits, int index) {if (index digits.size()) {result.push_back(s);return;}int digit digits[index] - 0; // 将index指向的数字转为intstring letters letterMap[digit]; // 取数字对应的字符集for (int i 0; i letters.size(); i) {s.push_back(letters[i]); // 处理backtracking(digits, index 1); // 递归注意index1一下层要处理下一个数字了s.pop_back(); // 回溯}}vectorstring letterCombinations(string digits) {s.clear();result.clear();if (digits.size() 0) {return result;}backtracking(digits, 0);return result;}
}; 思路 回溯算法
// 版本一
class Solution {
private:vectorvectorint result;vectorint path;void backtracking(vectorint candidates, int target, int sum, int startIndex) {if (sum target) {return;}if (sum target) {result.push_back(path);return;}for (int i startIndex; i candidates.size(); i) {sum candidates[i];path.push_back(candidates[i]);backtracking(candidates, target, sum, i); // 不用i1了表示可以重复读取当前的数sum - candidates[i];path.pop_back();}}
public:vectorvectorint combinationSum(vectorint candidates, int target) {result.clear();path.clear();backtracking(candidates, target, 0, 0);return result;}
};
优化代码 对总集合排序之后如果下一层的sum就是本层的 sum candidates[i]已经大于target就可以结束本轮for循环的遍历。
在求和问题中排序之后加剪枝是常见的套路
class Solution {
private:vectorvectorint result;vectorint path;void backtracking(vectorint candidates, int target, int sum, int startIndex) {if (sum target) {result.push_back(path);return;}// 如果 sum candidates[i] target 就终止遍历for (int i startIndex; i candidates.size() sum candidates[i] target; i) {sum candidates[i];path.push_back(candidates[i]);backtracking(candidates, target, sum, i);sum - candidates[i];path.pop_back();}}
public:vectorvectorint combinationSum(vectorint candidates, int target) {result.clear();path.clear();sort(candidates.begin(), candidates.end()); // 需要排序backtracking(candidates, target, 0, 0);return result;}
};
