39. Combination Sum
Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:
- All numbers (including target) will be positive integers.
- The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:
[
[7],
[2, 2, 3]
]
Description
本题要求从一个不重复序列中挑选出若干求和后与target相等的子序列，要求是每个元素可被选择无限次且返回的集合中不能有重复元素。
Analysis
典型的回溯法的应用，递归过程中，需要将每次的求和结果与目标值之间的差距作为参数来回传递，此外，由于能够使用之前用过的元素，所以在搜索过程中和以前的DFS算法也有所不同，具体体现在:递归调用时，递归深度并不+1，代码如下:
code
class Solution {
void backtracking(vector<vector<int>> & res,vector<int> & temp,vector<int> & candidates,int remain,int start){
if(remain<0) return;
if(remain==0){
res.push_back(temp);
return;
}
for(int i=start;i<candidates.size();++i){
temp.push_back(candidates[i]);
backtracking(res,temp,candidates,remain-candidates[i],i);//notice here
temp.pop_back();
}
}
public:
vector<vector<int>> combinationSum(vector<int> & candidates, int target) {
vector<int> temp;
vector<vector<int>> res;
backtracking(res,temp,candidates,target,0);
return res;
}
};