216. 组合总和 III
2024-08-30 04:40:59
216. 组合总和 III
题意
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。
说明:
所有数字都是正整数。
解集不能包含重复的组合。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解题思路
由于最终的结果要求是有序的,因此需要先将数组进行排序;
回溯:维持一个路径组合,并且不断的将target减去数组中的值,直到target值为0,则把路径组合加入到最终的结果中;
记忆化搜索:通过字典记录下每个和对应的组合,在target在不断减去数组中的值的时候,如果这个和已经出现过,那么直接返回该和对应的组合,由于新的组合是在前面的组合的基础上进行操作的,所以没有办法对前面的组合进行剪枝;
动态规划:应该也是和2类似的思想;
实现
之前以为回溯都需要有值返回
最新文章
- ios UIWebView自定义Alert风格的弹框
- OGG异常处理
- servlet、genericservlet、httpservlet之间的区别
- good books
- HDU 1176 免费馅饼(记忆化搜索)
- Android编程: 界面组成、事件监听器
- POJ1007
- IE9下报错,错误: “JSON”未定义
- [Cocos2d-x]Mac下运行HelloCpp For Android
- HashMap/HashSet,hashCode,哈希表
- springboot2.0整合es的异常总结
- 20175234 2018-2019-2 《Java程序设计》第八周学习总结
- Linux 创建静态库(.a)和动态库(.so)
- 《Linux内核设计与实现》第四章学习笔记
- 《全栈性能Jmeter》-5JMeter负载与监听
- 1分钟完美安装最新CentOS+Nginx+PHP-FPM+MySQL
- 【Hibernate】hibernate框架的搭建
- 《Python》 基础数据类型补充和深浅copy
- Java Log Viewer日志查看器
- SI - 系统 - 操作系统简述 (Operating System)