Leetcode 39. Combination Sum
文章作者：Tyan
博客：noahsnail.com | CSDN | 简书
1. Description
2. Solution
- Version 1
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
set<vector<int>> s;
sort(candidates.begin(), candidates.end());
vector<int> combination;
combinationSum(s, candidates, target, 0, combination);
return vector<vector<int>>(s.begin(), s.end());
}
private:
void combinationSum(set<vector<int>>& result, vector<int>& candidates, int& target, int sum, vector<int> combination) {
if(sum > target) {
return;
}
if(sum == target) {
sort(combination.begin(), combination.end());
result.insert(combination);
return;
}
for(int i = 0; i < candidates.size(); i++) {
combination.push_back(candidates[i]);
combinationSum(result, candidates, target, sum + candidates[i], combination);
combination.pop_back();
}
}
};
- Version 2
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> result;
sort(candidates.begin(), candidates.end());
vector<int> combination;
combinationSum(result, candidates, combination, target, 0, 0);
return result;
}
private:
void combinationSum(vector<vector<int>>& result, vector<int>& candidates, vector<int> combination, int& target, int sum, int begin) {
if(sum > target) {
return;
}
if(sum == target) {
result.push_back(combination);
return;
}
for(int i = begin; i < candidates.size(); i++) {
combination.push_back(candidates[i]);
combinationSum(result, candidates, combination, target, sum + candidates[i], i);
combination.pop_back();
}
}
};
- Version 3
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> result;
sort(candidates.begin(), candidates.end());
vector<int> combination;
combinationSum(result, candidates, combination, target, 0, 0);
return result;
}
private:
void combinationSum(vector<vector<int>>& result, vector<int>& candidates, vector<int> combination, int& target, int sum, int begin) {
if(sum > target) {
return;
}
if(sum == target) {
result.push_back(combination);
return;
}
for(int i = begin; i < candidates.size(); i++) {
combination.push_back(candidates[i]);
combinationSum(result, candidates, combination, target, sum + candidates[i], i);
combination.pop_back();
}
}
};