Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
Each number in candidates may only be used once in the combination.
Note:
- All numbers (including
target) will be positive integers. - The solution set must not contain duplicate combinations.
Example 1:
[10,1,2,7,6,1,5], target = 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
Example 2:
比起上个题多了个条件,结果不能重复,并且给定的元素有重复;
解决办法,在dfs的每层循环添加元素时,判断和前一个是不是相等,相等则不添加;
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end());
vector<vector<int>> res;
vector<int> tmp;
dfs(res,tmp,target,candidates,0);
return res;
}
void dfs(vector<vector<int>> &res, vector<int> &tmp, int target, vector<int> &candidates, int index)
{
if(0==target)
{
res.push_back(tmp);
return;
}
for(int i=index;i<candidates.size()&&candidates[i]<=target;++i) //注意加上 candidates<=targe, 否则容易超时
{
if(i!=index&&candidates[i]==candidates[i-1])continue;
tmp.push_back(candidates[i]);
dfs(res,tmp,target-candidates[i], candidates,i+1);
tmp.pop_back();
}
}
};