39. 组合总数
题目链接:https://leetcode-cn.com/problems/combination-sum/
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
dfs(candidates, target, 0, 0);
return res;
}
void dfs(vector<int>& candidates, int target, int u, int sum)
{
if(sum == target)
{
res.push_back(path);
return ;
}
//每次都从当前位置开始枚举下一个数,这样保证后面的数都是比前面大不会重复
for(int i = u; i < candidates.size(); i++)
{
if(sum + candidates[i] > target) break;
path.push_back(candidates[i]);
//从i开始枚举,保证当前数不会比前一个数大
dfs(candidates, target, i, sum + candidates[i]);
path.pop_back();
}
}
};
40. 组合总数II
题目链接:https://leetcode-cn.com/problems/combination-sum-ii/
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
dfs(candidates, target, 0, 0);
return res;
}
void dfs(vector<int>& candidates, int target, int u, int sum)
{
if(sum == target)
{
res.push_back(path);
return ;
}
for(int i = u; i < candidates.size(); i++)
{
if(i > u && candidates[i] == candidates[i - 1]) continue;
if(sum + candidates[i] > target) break;
path.push_back(candidates[i]);
//从i开始枚举,保证当前数不会比前一个数大
dfs(candidates, target, i + 1, sum + candidates[i]);
path.pop_back();
}
}
};
216. 组合总数III
题目链接: https://leetcode-cn.com/problems/combination-sum-iii/
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> combinationSum3(int k, int n) {
dfs(n, k, 1);
return res;
}
void dfs(int target, int k, int u)
{
if(!target && !k)
{
res.push_back(path);
return ;
}
for(int i = u; i <= 9; i++)
{
int tmp = target - i;
if(tmp < 0) break;
path.push_back(i);
dfs(tmp, k - 1, i + 1);
path.pop_back();
}
}
};