LeetCode-77-组合
2023-03-07 09:12:15 时间
# LeetCode-77-组合
给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合。
示例1:
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
# 解题思路
方法1、回溯:
典型的回溯题目,通过画一棵选择树不难看出,当有初始数组[1,2,3,4],k=2时
选择1之后,选择2,3,4能够组合成新的字串
选择2之后,选择3,4,能够组合成新的字串
可以归纳为,对于第i个选择的数,其和i+1开始到n的所有数进行组合,能够得到新的字串,且不会发生重复。
递归的终止条件为,k==2时,将字串添加进res中
当选择到达要求进行返回时,撤销上一次的选择,进行新的选择组合成新的字串
# Java代码
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<>();
backtrack(res, 1, n, k, new ArrayList<>());
return res;
}
private void backtrack(List<List<Integer>> res, int i, int n, int k, ArrayList<Integer> temp) {
if (k == temp.size()) {
res.add(new ArrayList<>(temp));
return;
}
for (int start = i; start < n + 1; start++) {
temp.add(start);
backtrack(res, start + 1, n, k, temp);
temp.remove(temp.size() - 1);
}
}
}
相关文章
- 在 Go 里用 CGO?这 7 个问题你要关注!
- 9款优秀的去中心化通讯软件 Matrix 的客户端
- 求职数据分析,项目经验该怎么写
- 在OKR中,我看到了数据驱动业务的未来
- 火山引擎云原生大数据在金融行业的实践
- OpenHarmony富设备移植指南(二)—从postmarketOS获取移植资源
- 《数据成熟度指数》报告:64%的企业领袖认为大多数员工“不懂数据”
- OpenHarmony 小型系统兼容性测试指南
- 肯睿中国(Cloudera):2023年企业数字战略三大趋势预测
- 适用于 Linux 的十大命令行游戏
- GNOME 截图工具的新旧截图方式
- System76 即将推出的 COSMIC 桌面正在酝酿大变化
- 2GB 内存 8GB 存储即可流畅运行,Windows 11 极致精简版系统 Tiny11 发布
- 迎接 ecode:一个即将推出的具有全新图形用户界面框架的现代、轻量级代码编辑器
- loongarch架构介绍(三)—地址翻译
- Go 语言怎么解决编译器错误“err is shadowed during return”?
- 敏捷:可能被开发人员遗忘的部分
- Denodo预测2023年数据管理和分析的未来
- 利用数据推动可持续发展
- 在 Vue3 中实现 React 原生 Hooks(useState、useEffect),深入理解 React Hooks 的