Combination Sum 要求target 在给定范围内的所有拆分,我是使用递归求解,先对向量进行排序,这样方便取数,以保证添加数的递增性质。
void myf(vector<vector<int> > &res,vector<int> &candidates, vector<int>re,int target,int i){
if (target==0) {res.push_back(re);return;}
if(target<0)return ;
int len=candidates.size();
for(;i<len;i++){
if(candidates[i]<=target){
re.push_back(candidates[i]);
myf(res,candidates ,re,target-candidates[i],i);
}else break;
re.pop_back();
}
}
class Solution {
public:
vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
int len=candidates.size();
vector<vector<int> > res;
vector<int >re;
sort(candidates.begin(),candidates.end());
myf(res,candidates ,re,target,0);
return res;
}
};
void myf(vector<vector<int> > &res,vector<int> &candidates, vector<int>re,int target,int i){
if (target==0) {
res.push_back(re);return;}
if(target<0)return ;
int len=candidates.size();
for(;i<len;i++){
if(candidates[i]<=target){
re.push_back(candidates[i]);
myf(res,candidates ,re,target-candidates[i],i+1);
}else break;
re.pop_back();
while(i<len&&candidates[i+1]==candidates[i])i++;
}
}
Combination Sum II 要求在上一题的基础上追加了每个数最多使用一次,其实这样将上一题代码稍加修改,就可以做到每个数只去一次,有个需要注意的问题是,相同的解可能会添加两次,因此对于相同的值,在每一轮递归使用时,要在所有相同值中,只使用第一个。
class Solution {
public:
vector<vector<int> > combinationSum2(vector<int> &num, int target) {
int len=num.size();
vector<vector<int> > res;
vector<int >re;
sort(num.begin(),num.end());
myf(res,num ,re,target,0);
return res;
}
};