Combination Sum
Description
Given a set of candidate numbers (candidates
) (without duplicates) and a target number (target
), find all unique combinations in candidates
where the candidate numbers sums to target
.
The same repeated number may be chosen from candidates
unlimited number of times.
Note:
All numbers (including
target
) will be positive integers.The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]
Example 2:
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
Solution
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<int> nums;
vector<vector<int>> ans;
dfs(candidates, 0, target, nums, ans);
return ans;
}
void dfs(vector<int> &candidates, int k, int target, vector<int> &nums, vector<vector<int>> &ans){
if(target == 0){
ans.push_back(nums);
return;
}
if(k == candidates.size() || target < 0) return;
int size = nums.size();
int num = candidates[k];
// use 0, 1, 2, ... candidates[i]
for(int j = 0; j * num <= target; ++j){
dfs(candidates, k + 1, target - j * num, nums, ans);
nums.push_back(num);
}
nums.resize(size);
}
};
Last updated