思路:
- 利用回溯,其运行过程可以看成遍历一颗4叉树(因为要求不重复,所以中间剪掉了部分树枝),复杂度为(O(n^h)),(h)为树的高度,这里(h)相当于只用数组里最小的数加起来大于等于target时所用的数目。比如[2,3,6,7],target = 7。2+2+2+2 > 7,所以h为4。
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> res;
vector<int> tmp;
backtrace(res,tmp,candidates,0,target,0);
return res;
}
void backtrace(vector<vector<int>>& res,vector<int>& tmp,vector<int> nums,int sum,int target,int start){
if(sum > target) return;
if(sum == target) res.push_back(tmp);
else{
for(int i = start; i < nums.size(); i++){
tmp.push_back(nums[i]);
backtrace(res,tmp,nums,sum+nums[i],target,i); //使用i避免了重复情况
tmp.pop_back();
}
}
}
};