Description
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.
Example
For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:
[
[7],
[2, 2, 3]
]思路
- dfs
- 按照下图方式剪枝，可保证没有重复
代码
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> res;
sort(candidates.begin(), candidates.end());
vector<int> tmp;
dfs(candidates, target, candidates.size(), 0, res, tmp, 0);
return res;
}
bool dfs(vector<int> &candidates, int target, int len, int t, vector<vector<int>> &res, vector<int> &tmp, int sum){
if (sum == target){
res.push_back(tmp);
return true;
}
else if (sum < target){
for (int i = t; i < len; ++i){
if (sum + candidates[i] > target) return false;
sum += candidates[i];
tmp.push_back(candidates[i]);
bool flag = dfs(candidates, target, len, i, res, tmp, sum);
sum -= candidates[i];
tmp.pop_back();
if (flag){
break;
}
}
}
return false;
}
};内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
