Given a set of candidate numbers (C) 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]
]找出和为target的组合，每个数可重复使用，和POJ上一道搜索剪枝类似。
如果是求出所有组合的数量，肯定是DP，但是应为要求出具体组合，所以还是DFS好使。
注意剪枝条件：
1.排序，先搜大的，大的数可变性比较小，可以有效减少搜索空间
2.去除重复的数，这个也是在交完才发现的。
代码语言：javascript复制class Solution {
public:
void dfs(vector<int>& candidates,int target,vector<vector<int>>& result,vector<int> path,int limit)
{
if(target==0)
{
result.push_back(path);
return ;
}
for(int i=candidates.size()-1;i>=0;i--)
{
if(candidates[i]>target || i>limit) continue;
path.push_back(candidates[i]);
dfs(candidates,target-candidates[i],result,path,i);
path.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target)
{
vector<vector<int>> result;
vector<int> path;
sort(candidates.begin(),candidates.end());
for(int i=0;i<candidates.size();i )
if(i<(candidates.size()-1) && candidates[i]==candidates[i 1])
{
candidates.erase(candidates.begin() i);
i--;
}
dfs(candidates,target,result,path,candidates.size()-1);
return result;
}
};
