博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
leetcode----216. Combination Sum III
阅读量:4113 次
发布时间:2019-05-25

本文共 885 字,大约阅读时间需要 2 分钟。

链接:

大意:

给定一个数k和一个数n,要求从1-9中找出k个不同的数,其和为n。求出所有这样的组合。注意:每个数字在一个组合内只能被使用一次。例子:

思路:

经典的回溯。具体思路看代码。

代码:

class Solution {    public List
> combinationSum3(int k, int n) { List
> res = new ArrayList<>(); // k个0-9的数最小的和为(1 + k) * k / 2 最大的和为 (19 - k) * k / 2 int minSum = (1 + k) * k / 2, maxSum = (19 - k) * k / 2; if (n < minSum || n > maxSum) return res; dfs(k, n, 1, res, new ArrayList<>()); return res; } public void dfs(int k, int n, int idx, List
> res, List
list) { // 当收集到k个数时无论这k个数的和是否等于n 都会return if (k == list.size()) { if (n == 0) { res.add(new ArrayList<>(list)); } return ; } while (idx <= 9) { // 剪枝 if (n - idx < 0) break; list.add(idx); dfs(k, n - idx, idx + 1, res, list); list.remove(list.size() - 1); // 回溯 idx++; } }}

结果:

结论:

经典回溯题,掌握回溯的模板就ok

 

 

转载地址:http://iaesi.baihongyu.com/

你可能感兴趣的文章
LeetCode第46题思悟——全排列(permutations)
查看>>
LeetCode第47题思悟—— 全排列 II(permutations-ii)
查看>>
LeetCode第48题思悟——旋转图像(rotate-image)
查看>>
驱动力3.0,动力全开~
查看>>
记CSDN访问量10万+
查看>>
Linux下Oracle数据库账户被锁:the account is locked问题的解决
查看>>
记CSDN访问20万+
查看>>
Windows 环境下Webstorm 2020.3 版本在右下角找不到Git分支切换部件的一种解决方法
查看>>
Electron-Vue项目中遇到fs.rm is not a function问题的解决过程
查看>>
飞机换乘次数最少问题的两种解决方案
查看>>
有向无回路图的理解
查看>>
设计模式中英文汇总分类
查看>>
MFC实现五子棋游戏
查看>>
WPF实现蜘蛛纸牌游戏
查看>>
单例模式
查看>>
工厂方法模式
查看>>
模板方法模式
查看>>
数据结构之队列、栈
查看>>
数据结构之树
查看>>
数据结构之二叉树
查看>>