深圳网站托管,海门网站建设,网站开发源代码知识产权归属,济南房产网二手房可能需要回顾的文章; leetcode 77. 组合 思考分析 1、题目
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数#xff0c;并且每种组合中不存在重复的数字。 说明#xff1a; 所有数字都是正整数。 解集不能包含重复的组合。
2、递归
这一题和之前… 可能需要回顾的文章; leetcode 77. 组合 思考分析 1、题目
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数并且每种组合中不存在重复的数字。 说明 所有数字都是正整数。 解集不能包含重复的组合。
2、递归
这一题和之前一题很像 leetcode 77. 组合 思考分析 终止条件有两个sumn res.size() k 回溯的过程中加入对sum值的修改。 修改一下递归函数的参数值这样本题就做好了
class Solution {
public:vectorvectorint result;vectorint res;int sum;void clear_solution_param(){result.clear();res.clear();sum0;}void backtracking(int start,int end,int k,int n){//找到了k个数if(res.size() k sum n){result.push_back(res);return;}for(int istart;iend;i){//处理结点res.push_back(i);sumi;//递归,探索下一层backtracking(i1,end,k,n); //递归sum-i;//回溯撤销处理结果res.pop_back();}}vectorvectorint combinationSum3(int k, int n) {clear_solution_param();backtracking(1,9,k,n);return result;}
};3、剪枝优化
1、我们之前的终止条件其实限的有问题如果res.size已经等于k了那么就没必要继续搜索了直接返回。sum是否等于n只是关系到我们是否得到正确答案。所以应该修改为
if(res.size() k)
{if(sum n) result.push_back(res);return; //如果sizek,但是sum!n直接返回
}2、修改成上面那样其实还是有冗余我们注意到如果sumn此时也没有必要进行再次搜索了
if(sumn) return;
if(res.size() k)
{if(sum n) result.push_back(res);return; //如果sizek,但是sum!n直接返回
}3、同leetcode 77. 组合 思考分析的剪枝操作 我们已经选择的元素个数为res.size() 我们还需要的元素的个数为k-res.size() 所以最多从end-(k-res.size())1的地方开始遍历。
for(int istart;iend-(k-res.size())1;i)
{//处理结点res.push_back(i);sumi;//递归,探索下一层backtracking(i1,end,k,n); //递归sum-i;//回溯撤销处理结果res.pop_back();
}4、最终代码
class Solution {
public:vectorvectorint result;vectorint res;int sum;void clear_solution_param(){result.clear();res.clear();sum0;}void backtracking(int start,int end,int k,int n){if(sumn) return;if(res.size() k){if(sum n) result.push_back(res);return; //如果sizek,但是sum!n直接返回}for(int istart;iend-(k-res.size())1;i){//处理结点res.push_back(i);sumi;//递归,探索下一层backtracking(i1,end,k,n); //递归sum-i;//回溯撤销处理结果res.pop_back();}}vectorvectorint combinationSum3(int k, int n) {clear_solution_param();backtracking(1,9,k,n);return result;}
};
