慢慢刷题有点熟练了也开始做一些以前不会做的题目,这就有一题叫做 组合总和的问题
题目
给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明:
所有数字(包括 target)都是正整数。
解集不能包含重复的组合。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/combination-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
可以分析一下题目,首先这是一个无重复数字的数组,所以可以尽情放飞自我,一开始看到这个题目我立刻想到了递归回溯,因此代码很快就瞎写出来
class Solution {
public:
vector<vector<int>> result; //储存结果
void backTrace(vector<int>& candidates,int target,vector<int> now,int sum)
{
if(sum==target) //如果总和等于目标,将当前容器添加到结果中
{
result.push_back(now);
return;
}
if(sum>target) //如果总和大于目标,直接返回
return;
for(int i=0;i<candidates.size();i++) //依次对所有内容进行插入尝试
{
now.push_back(candidates[i]); //插入元素
backTrace(candidates,target,now,sum+=candidates[i]); //调用
now.pop_back(); //弹出元素
sum-=candidates[i];
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<int> now;
backTrace(candidates,target,now,0);
return result;
}
};
结果出来后却跟预期结果有所出入,内容是对了,但是却有赘余
可以看出来第一个结果[2,2,3]而我的结果中多了两个,相当于给[2,2,3]来了一次全排列,,因为题目要求解集不能包含重复的组合,因此这样肯定不行
解决方法
在参考了LeetCode的官方题解后,我注意到了一个词
剪枝
看到他的那张图,我立刻明白了,这题中需要运用到剪枝,将多余的结果剪掉,与其说是剪掉不如说就是避免重复结果的产生
题解中是这样说的
- 在搜索的时候需要设置搜索起点的下标begin,下一层的节点从这个搜索起点开始搜索
- 在搜索起点begin之前的数因为以前的分支搜索过了,所以一定会产生重复
瞬间理解了要表达的意思,并修改了代码
AC代码
class Solution {
public:
vector<vector<int>> result;
//在函数中添加了begin变量用于剪枝
void backTrace(vector<int>& candidates,int target,vector<int> now,int sum,int begin)
{
if(sum==target)
{
result.push_back(now);
return;
}
if(sum>target)
return;
//从给定的begin开始搜索,以避免产生重复组合
for(int i=begin;i<candidates.size();i++)
{
now.push_back(candidates[i]);
backTrace(candidates,target,now,sum+=candidates[i],i);
now.pop_back();
sum-=candidates[i];
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<int> now;
backTrace(candidates,target,now,0,0);
return result;
}
};
总结
运行用时和内存消耗的结果不是特别好,只战胜了百分之十几的人,不过AC就好,而且还学到了新知识,以后遇到类似问题就能迎刃而解了
话说之前好像做到过类似的题目没做出来,秒回去做题
Q.E.D.
Comments | 0 条评论