【算法】【搜索和回溯】Leetcode组合总和
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【算法】【搜索和回溯】Leetcode组合总和,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1829字,纯文字阅读大概需要3分钟。
内容图文
![【算法】【搜索和回溯】Leetcode组合总和](/upload/InfoBanner/zyjiaocheng/627/b9bc9f5e6b344ff0932b6f558cf7270e.jpg)
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();
}
}
};
内容总结
以上是互联网集市为您收集整理的【算法】【搜索和回溯】Leetcode组合总和全部内容,希望文章能够帮你解决【算法】【搜索和回溯】Leetcode组合总和所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。