LeetCode笔记:216. Combination Sum III
2023-03-15 23:23:39 时间
问题:
Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers. Example 1: Input: k = 3, n = 7 Output: [[1,2,4]] Example 2: Input: k = 3, n = 9 Output: [[1,2,6], [1,3,5], [2,3,4]]
大意:
找到所有可能的k个数字相加得到n的组合,只有1到9这些数字可以用,并且组合中的每个数字必须都只使用一次。 例1: 输入:k = 3,n = 7 输出: [[1,2,4]] 例2: 输入:k = 3,n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]
思路:
题目有几个要求,数字个数必须为k,只能用1到9这些数字,每个组合里数字不能重复,数字相加为n。
因为可能性有很多,我们用递归来做。
因为只能用1到9的数字,我们就从1到9分别遍历,依次以某个数字开始,往后找进行加数字,每递归一次,后面还有多少个数字就有多少种组合的方法,所以其实组合的方法有987*6....每次递归我们判断成功的条件是目前加起来的和正好等于目的数字n,且组合中的数字个数正好为k。如果我们用到的数字超过9了或者个数超过k了,就不要继续递归了。注意每次递归时因为要循环使用参数,所以我们每次都要创建新的变量来进行操作,避免影响参数本身的值。
代码(Java):
public class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
for (int i = 1; i <= 9; i++) {
int sum = i;
List<Integer> list = new ArrayList<Integer>();
list.add(i);
find(k-1, n, list, sum, i+1, res);
}
return res;
}
public void find(int k, int n, List<Integer> list, int sum, int start, List<List<Integer>> res) {
if (sum == n && k == 0) {
res.add(list);
} else if (sum < n) {
if (k <= 0 || start > 9) return;
else {
for (int i = start; i <= 9; i++) {
int newSum = sum;
newSum += i;
List<Integer> newList = new ArrayList<Integer>();
newList.addAll(list);
newList.add(i);
find(k-1, n, newList, newSum, i+1, res);
}
}
}
}
}
相关文章
- GitHub换帅!开源大神辞任CEO,竞品GitLab刚完成IPO
- 每日一题---蓝桥杯“关联矩阵”
- 后端入门---Servlet乱码问题的解决
- react + zarm 实现账单列表展示页
- 码云---推送本地文件到远程仓库
- 用数学方式打开Facebook新Logo,真的和视频号Logo来自同一方程
- IRF堆叠使用问题分析
- 谷歌启动AlphaFold商业化:成立新公司,专注AI新药开发技术
- 随笔---使用navicat浮点型(float)自动转为整数的解决办法
- 他89岁,拿下人生第3个博士学位,横跨医学物理学,只为“实现儿时梦想”
- eggjs 怎么实现获取账单类型字典接口?
- 中国医疗AI第一股首位投资人:AI不再高深,正在回归商业本质
- NVIDIA JetBot系列教程(3):无线WIFI的安装与调试(上)
- 魔改GPT自动写网文,速度一秒十字,还能给太监作品无限续更 | 开源
- react + zarm 实现账单列表类型以及时间条件弹窗封装
- 阿里云与 Kubecost 合作,容器服务 ACK 支持使用 Kubecost 进行成本管理
- SpringCloud Alibaba学习(二):Nacos之服务配置中心
- 机器狗常州巡逻防疫,喊话“不扎堆不聚集”,网友:给孩子安个狗头吧
- error: Two output files share the same path but have different contents: node_modules\.vite\..xxx.js
- Emotet恶意软件回归、黑客入侵FBI电子邮件系统|11月16日全球网络安全热点