回溯算法:求组合问题!
2023-03-14 09:34:43 时间
回溯算法大家是不是已经快忘了,还记得组合问题应该怎么求了么?哈哈哈
回溯算法其实就是暴力搜索,既然是暴力搜索为什么要非要用回溯呢?因为一些问题能暴力搜索出就不错了,找不出更好的办法。
给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合。
如果用for循环嵌套一层一层去解决这个问题,如果n为100,k为50呢,那就50层for循环,此时就发现单纯的暴力不可以了。
回溯算法就登场了。
回溯算法中的用递归来做for循环层叠嵌套(可以理解是开k层for循环)
每一次的递归中嵌套一个for循环,那么递归就可以解决多层嵌套循环的问题了。
我在文章回溯算法:求组合问题! 中,同时还给出了回溯三部曲。按照这个方法来,就发现回溯算法其实并不难咯。
题目链接:https://leetcode-cn.com/problems/combinations/
回溯算法模板如下:
- void backtracking(参数) {
- if (终止条件) {
- 存放结果;
- return;
- }
- for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
- 处理节点;
- backtracking(路径,选择列表); // 递归
- 回溯,撤销处理结果
- }
- }
本文转载自微信公众号「代码随想录」,可以通过以下二维码关注。转载本文请联系代码随想录公众号。
相关文章
- 在 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 的