Leetcode dfs Combination SumII
2024-08-26 07:42:15
Combination Sum II
Total Accepted: 13710 Total
Submissions: 55908My Submissions
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where
the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:
- All numbers (including target) will be positive integers.
- Elements in a combination (a1, a2,
… , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤
… ≤ ak). - The solution set must not contain duplicate combinations.
For example, given candidate set 10,1,2,7,6,1,5
and
target 8
,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]
题意:给定一组数C和一个数值T,在C中找到全部总和等于T的组合。
C中的同一数字最多仅仅能拿一次。找到的组合不能反复。
思路:dfs
第i层的第j个节点有 n - i - j 个选择分支
递归深度:递归到总和大于等于T就能够返回了
复杂度:时间O(n!),空间O(n)
vector<vector<int> > res;
vector<int> _num;
void dfs(int start, int target, vector<int> &path){
if(target == 0) {res.push_back(path); return;}
int previous = -1; //这里要加上这个来记录同一层分枝的前一个值。假设当前值跟前一个值一样。就跳过,避免反复
for(int i = start; i < _num.size(); ++i){
if(previous == _num[i]) continue;
if(target < _num[i]) return; //剪枝
previous = _num[i];
path.push_back(_num[i]);
dfs(i + 1, target - _num[i], path);
path.pop_back();
}
}
vector<vector<int> > combinationSum2(vector<int> &num, int target){
_num = num;
sort(_num.begin(), _num.end());
vector<int> path;
dfs(0, target, path);
return res;
}
版权声明:本文博客原创文章。博客,未经同意,不得转载。
最新文章
- entiryFramework 事务控制
- Android开发资料学习(转载/链接)
- PHP条件语句语法与示例
- [转载] C++ 突破私有成员访问限制
- 常用IT类英文词汇 - 1
- html中rel标签是什么意思
- iOS开发 - 一个天真的搜索控制器的独白
- django --fields.E304 错误解决方案
- 阿里云容器服务--配置自定义路由服务应对DDOS攻击
- PHP 易出问题记录
- python的数与字符串
- 在Qt中用QAxObject来操作Excel
- java-retry实现
- 《SpringMVC从入门到放肆》七、模型与视图ModelAndView
- 818C.soft thief
- Android项目创建.prorperties配置文件和调用方法
- Linux中利用grep命令如何检索文件内容详解
- Nginx 学习笔记(三)proxy_cache 缓存配置和ngx_cache_purge模块
- 【CJOJ2375】 【HZOI 2015】偏序 II(cdq分治,树状数组)
- Linux下oracle定时备份
热门文章
- 使用SKIP-GRANT-TABLES 解决 MYSQL ROOT密码丢失(转)
- directx11编程中遇到的错误及解决方法
- partial 的好处
- C++包括头文件&;lt;&;gt;和&;quot;&;quot;差额
- The area面积计算
- 输出A打头的字符串
- Apple Watch 1.0 开发介绍 1.4 简介 使用iOS技术
- 在前端一定要了解的HTML,CSS知识
- 对比Windows 8模拟器(Simulator)和Windows Phone仿真器(Emulator)
- ProgressMonitorInputStream