天津市城乡建设部网站首页,创网通信科技有限公司,永久免费linux云主机,教育企业重庆网站建设目录1、题目2、思考分析3、未经优化代码4、剪枝优化1、题目
给定一个无重复元素的数组 candidates 和一个目标数 target #xff0c;找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取。
2、思考分析
解空间树宽度部分即数…
目录1、题目2、思考分析3、未经优化代码4、剪枝优化1、题目
给定一个无重复元素的数组 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取。
2、思考分析
解空间树宽度部分即数组 candidates内集合深度取决于target. 一开始的重复元素理解错误了每层循环都从0开始 for(int i0;icandidates.size();i) 这样是不对的会产生重复组合。 我们仍然需要采用startindex作为for起始位置不过对于下一层我们的startindex不是startindex1而是仍然是startindex这样才能重复取相同元素。
图1 for从0开始 图2 for从i开始
3、未经优化代码
class Solution {
public:vectorvectorint result;vectorint res;int sum;void clear_solution_param(){result.clear();res.clear();sum0;}void backtracking(vectorint candidates,int startindex,int n){ if(sum n) return;if(sum n){result.push_back(res);return;}for(int istartindex;icandidates.size();i){//处理结点res.push_back(candidates[i]);sumcandidates[i];//递归,探索下一层backtracking(candidates,i,n); //递归sum-candidates[i];//回溯撤销处理结果res.pop_back();}}vectorvectorint combinationSum(vectorint candidates, int target) {clear_solution_param();backtracking(candidates,0,target);return result;}
};4、剪枝优化
先对数组进行排序这样集合元素排列就是有序的了方便剪枝。这个在回溯法中经常用到 对于同一层的for循环如果sum加上此时的候选元素的和大于target则没有必要继续深入下去了。
class Solution {
public:vectorvectorint result;vectorint res;int sum;void clear_solution_param(){result.clear();res.clear();sum0;}void backtracking(vectorint candidates,int startindex,int n){ if(sum n) return;if(sum n){result.push_back(res);return;}for(int istartindex;icandidates.size();i){//由于输入的数组是有序的所以直接进行剪枝。如果sum加上这个集合元素大于目标此层就不需要往后看了因为后面的元素加上sum肯定大于目标if(sumcandidates[i]n) break;//处理结点res.push_back(candidates[i]);sumcandidates[i];//递归,探索下一层backtracking(candidates,i,n); //递归sum-candidates[i];//回溯撤销处理结果res.pop_back();}}vectorvectorint combinationSum(vectorint candidates, int target) {clear_solution_param();//排序加速剪枝sort(candidates.begin(),candidates.end());backtracking(candidates,0,target);return result;}
};
