网站建设w亿玛酷1流量订制,深圳市宝安区投资推广署官网,英文版科技网站,淘宝客网站做好了该怎么做什么是回溯算法#xff1f; 回溯算法也可以叫回溯搜索算法#xff0c;回溯是递归的副产品,回溯的本质是穷举#xff0c;然后选出我们需要的数据#xff0c;回溯本身不是特别高效的算法#xff0c;但我们可以通过剪枝来优化它。 理解回溯算法 回溯…什么是回溯算法 回溯算法也可以叫回溯搜索算法回溯是递归的副产品,回溯的本质是穷举然后选出我们需要的数据回溯本身不是特别高效的算法但我们可以通过剪枝来优化它。 理解回溯算法 回溯算法的解决可以模拟成树的结构因为回溯法解决的是在集合中递归搜索子集的过程集合的大小构成树的宽度递归的深度构成树的深度。 回溯算法模板
确定回溯算法的返回值与参数(一般先写逻辑然后需要什么参数就增加什么参数)确定回溯函数的终止条件确定回溯搜查的遍历过程
void BackTracking(参数)
{if (终止条件){处理结果return;}for (选择本层集合中的元素树中节点孩子的数量就是集合的大小){处理节点BackTracking(路径选择列表);//递归回溯撤销处理结果}
}组合
问题 给定两个整数 n 和 k返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 来源力扣LeetCode组合 思路一这种题目我们一眼就能想到使用for循环套循环比如 k2时 int n 4;for (int i 1; i n; i){for (int j i 1; j n; j){//处理结果}}但是如果k越来越大我们套用的循环也会越来越多这种暴力解法无疑是不现实的。
思路二我们在前面说过可以使用树的结构来模拟回溯递归的过程 比如n4 k2 树的初始集合是[1,2,3,4],从左向右取取过的数不再取每次从集合中选取元素可选择的范围逐渐缩小。有图可以发现n相当于树的宽度而k相当于树的深度。我们再由模板来写出最终代码
class Solution {
public:vectorvectorint arr;//存放符合条件的集合vectorint _arr;//用来存放符合条件的单一数据void BackTracking(int n, int k, int begin){if (_arr.size() k)//递归终止条件{arr.push_back(_arr);//单一数据存放至总集合里return;}for (int i begin; i n; i)//控制树的横向遍历{_arr.push_back(i);//处理节点BackTracking(n, k, i 1);//递归控制树的纵向遍历即深度_arr.pop_back();//回溯撤销处理的节点}}vectorvectorint combine(int n, int k) {BackTracking(n, k, 1);return arr;}
};剪枝优化
如果出现下面情况 n4 k4 那么在第一层for循环中从元素2开始的遍历都没有意义因为满足k的数量不够了所以有图可知打叉的地方都可以优化掉 优化过程
已经选择的元素个数_arr.size()还需要的元素个数k - _arr.size()
优化后的代码
class Solution {
public:vectorint _arr;vectorvectorint arr;void BackTracking(int n, int k, int begin){if (_arr.size() k){arr.push_back(_arr);return;}for (int i begin; i n-(k-_arr.size())1; i)//剪枝优化{_arr.push_back(i);BackTracking(n, k, i 1);_arr.pop_back();}}vectorvectorint combine(int n, int k) {BackTracking(n, k, 1);return arr;}
};组合总和 III
问题 找出所有相加之和为 n 的 k 个数的组合且满足下列条件
只使用数字1到9每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次组合可以以任何顺序返回。 来源力扣LeetCode组合总和 III 思路这个题相对于上一个题来说就是k为树的深度而集合固定为1到9也就是树的宽度为9 比如k2 只取两个数 代码
class Solution {
public:vectorvectorint arr;vectorint _arr;void BackTracking(int k,int n,int begin,int sum){if(_arr.size()k)//终止条件{if(sumn)//满足题意{arr.push_back(_arr);}return;}for(int ibegin;i9;i)//横向遍历{sumi;//收集元素总和_arr.push_back(i);//收集元素BackTracking(k,n,i1,sum);//递归纵向遍历sum-i;//回溯_arr.pop_back();//回溯}}vectorvectorint combinationSum3(int k, int n) {BackTracking(k,n,1,0);return arr;}
};剪枝优化
如果我们选择的元素总和已经大于n那么我们再往后遍历的总和肯定也大于n就没有继续遍历下去的意义了。元素个数方面同样与上一题一样能继续优化。 优化后
class Solution {
public:vectorvectorint arr;vectorint _arr;void BackTracking(int k,int n,int begin,int sum){if(sumn)//剪枝条件{return;}if(_arr.size()k){if(sumn){arr.push_back(_arr);}return;}for(int ibegin;i9-(k-_arr.size())1;i)//元素个数的优化{sumi;_arr.push_back(i);BackTracking(k,n,i1,sum);sum-i;_arr.pop_back();}}vectorvectorint combinationSum3(int k, int n) {BackTracking(k,n,1,0);return arr;}
};
