当前位置: 首页 > news >正文

代码随想录算法训练营第二十四天|● 理论基础 ● 77. 组合

仅做学习笔记,详细请访问代码随想录

● 理论基础
● 77. 组合

● 理论基础

回溯法解决的问题
回溯法,一般可以解决如下几种问题:

组合问题:N个数里面按一定规则找出k个数的集合
切割问题:一个字符串按一定规则有几种切割方式
子集问题:一个N个数的集合里有多少符合条件的子集
排列问题:N个数按一定规则全排列,有几种排列方式
棋盘问题:N皇后,解数独等等

回溯法模板
这里给出Carl总结的回溯算法模板。

在讲二叉树的递归 (opens new window)中我们说了递归三部曲,这里我再给大家列出回溯三部曲。

回溯函数模板返回值以及参数
在回溯算法中,我的习惯是函数起名字为backtracking,这个起名大家随意。

回溯算法中函数返回值一般为void。

再来看一下参数,因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来,所以一般是先写逻辑,然后需要什么参数,就填什么参数。

但后面的回溯题目的讲解中,为了方便大家理解,我在一开始就帮大家把参数确定下来。

回溯函数伪代码如下:

void backtracking(参数)
回溯函数终止条件
既然是树形结构,那么我们在讲解二叉树的递归 (opens new window)的时候,就知道遍历树形结构一定要有终止条件。

所以回溯也有要终止条件。

什么时候达到了终止条件,树中就可以看出,一般来说搜到叶子节点了,也就找到了满足条件的一条答案,把这个答案存放起来,并结束本层递归。

所以回溯函数终止条件伪代码如下:

if (终止条件) {
存放结果;
return;
}
回溯搜索的遍历过程
在上面我们提到了,回溯法一般是在集合中递归搜索,集合的大小构成了树的宽度,递归的深度构成的树的深度。

如图:
在这里插入图片描述
注意图中,我特意举例集合大小和孩子的数量是相等的!

回溯函数遍历过程伪代码如下:

for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
处理节点;
backtracking(路径,选择列表); // 递归
回溯,撤销处理结果
}
for循环就是遍历集合区间,可以理解一个节点有多少个孩子,这个for循环就执行多少次。

大家可以从图中看出for循环可以理解是横向遍历,backtracking(递归)就是纵向遍历,这样就把这棵树全遍历完了,一般来说,搜索叶子节点就是找的其中一个结果了。

分析完过程,回溯算法模板框架如下:

void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}

for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {处理节点;backtracking(路径,选择列表); // 递归回溯,撤销处理结果
}

}

● 77. 组合

class Solution {
private:vector<vector<int>> result; // 存放符合条件结果的集合vector<int> path; // 用来存放符合条件结果void backtracking(int n, int k, int startIndex) {if (path.size() == k) {result.push_back(path);return;}for (int i = startIndex; i <= n; i++) {path.push_back(i); // 处理节点backtracking(n, k, i + 1); // 递归path.pop_back(); // 回溯,撤销处理的节点}}
public:vector<vector<int>> combine(int n, int k) {result.clear(); // 可以不写path.clear();   // 可以不写backtracking(n, k, 1);return result;}
};

相关文章:

代码随想录算法训练营第二十四天|● 理论基础 ● 77. 组合

仅做学习笔记&#xff0c;详细请访问代码随想录 ● 理论基础 ● 77. 组合 ● 理论基础 回溯法解决的问题 回溯法&#xff0c;一般可以解决如下几种问题&#xff1a; 组合问题&#xff1a;N个数里面按一定规则找出k个数的集合 切割问题&#xff1a;一个字符串按一定规则有几…...

买保险如何填健康告知

在投保健康险时&#xff0c;保险公司都有健康告知这一环&#xff0c;那么健康告知怎么机智的填&#xff1f; 人都吃五谷杂粮&#xff0c;身体免不了有各种小毛病&#xff0c;比如甲状腺结节等&#xff0c;健康告知通过不了怎么办&#xff1f; 健康告知是保险公司设计的健康问…...

云贝教育 | 【技术文章】Oracle 19c RAC修改网络

注: 本文为云贝教育 刘峰 原创&#xff0c;请尊重知识产权&#xff0c;转发请注明出处&#xff0c;不接受任何抄袭、和未经注明出处的转载。 原文链接&#xff1a;【Oracle 19c】Oracle 19c RAC修改网络 - 课程体系 - 云贝教育 (yunbee.net) 变更目标 ip类型 节点 原IP 目…...

Android SELinux:保护您的移动设备安全的关键

Android SELinux&#xff1a;保护您的移动设备安全的关键 1 引言 移动设备在我们的生活中扮演着越来越重要的角色&#xff0c;我们几乎把所有重要的信息都存储在这些设备上。然而&#xff0c;随着移动应用程序的数量不断增加&#xff0c;安全性也变得越来越关键。这就是为什么…...

第十三章认识Ajax(四)

认识FormData对象 FormData对象用于创建一个表示HTML表单数据的键值对集合。 它可以用于发送AJAX请求或通过XMLHttpRequest发送表单数据。 以下是FormData对象的一些作用: 收集表单数据:通过将FormData对象与表单元素关联,可以方便地收集表单中的数据。使用FormData对象,…...

使用 Node.js 和 Cheerio 爬取网站图片

写一个关于图片爬取的小案例 爬取效果 使用插件如下&#xff1a; {"dependencies": {"axios": "^1.6.0","cheerio": "^1.0.0-rc.12","request": "^2.88.2"} }新建一个config.js配置文件 // 爬取图片…...

2024美赛数学建模E题思路源码

赛题目的 可以将其拆解为以下主要问题&#xff0c;并为每个问题提出解决方案&#xff1a; 如何在极端天气事件越来越多的地区部署财产保险&#xff1f; 保险公司应在何时何地承保保单&#xff1f; 业主如何影响保险公司的承保决定&#xff1f; 如何建立能够评估未来房地产决…...

解决Docker AList本地挂载失效的问题。

解决Docker AList本地挂载失效的问题。 AList Docker version: 3.3 services:alist:image: xhofe/alist:latestcontainer_name: alistvolumes:- ./etc/alist:/opt/alist/data# 比如我要挂载/home,如果在docker里先挂载&#xff0c;是没法办法映射到linux系统下的/home的- /ho…...

Emmet常用语法总结

Emmet常用语法总结 子元素&#xff1a;>兄弟元素&#xff1a;上级元素&#xff1a;^倍数&#xff1a;*分组&#xff1a;&#xff08;&#xff09;属性&#xff1a;[]id和类&#xff1a;# .迭代数字&#xff1a;$文本内容&#xff1a;{}注意事项 Emmet是许多流行文本编辑器的…...

Android 12系统源码_页面管理(四)获取系统当前最上层的Activity信息

前言 很多应用开发人员&#xff0c;在日常开发过程中&#xff0c;经常会遇到一些需求&#xff0c;例如需要知道当前最上层的Activity是哪个&#xff0c;并结合这个Activity的名称来完成一些特定场景的需求。最简单的方法&#xff0c;是在创建Activity的时候将该Actvity存储到一…...

RK3588开发板Ubuntu与开发板使用U盘互传

1 将 U 盘(U 盘的格式必须为 FAT32 格式&#xff0c;大小在 32G 以下)插到开发板的 usb 接口&#xff0c;串口打印信息如下所示&#xff0c;U 盘的设备节点是/dev/sdb4。U 盘的设备节点不是固定的&#xff0c;根据实际情况来查看设备节点。 2 输入以下命令挂载 U 盘&#xff0c…...

【BUG】golang gorm导入数据库报错 “unexpected type clause.Expr“

帮同事排查一个gorm导入数据报错的问题 事发现场 ck sql CREATE TABLE ods_api.t_sms_jg_msg_callback_dis (app_key String DEFAULT COMMENT 应用标识,callback_type Int32 DEFAULT 0 COMMENT 0送达&#xff0c;1回执,channel Int32 DEFAULT 0 COMMENT uid下发的渠道,mode…...

TCP/IP网络模型

大家好我是苏麟 , 今天聊聊TCP/IP四层网络模型 . 资料来源 : 小林coding 小林官方网站 : 小林coding (xiaolincoding.com) 应用层 最上层的&#xff0c;也是我们能直接接触到的就是应用层&#xff08;Application Layer&#xff09;&#xff0c;我们电脑或手机使用的应用软件都…...

github连不上

github连不上 错误提示解决方案steam 采用Hosts加速 错误提示 fatal: unable to access ‘https://github.com/Ada-design/qianduan.git/’: Failed to connect to github.com port 443 after 21073 ms: Couldn’t connect to server 解决方案 下载steam https://steampp.ne…...

Excel计算表达式的值

Excel如何求解表达式 其中第三种方法最简单&#xff0c;通过剪贴板实现 如&#xff0c;单元格A1中输入了 12345 然后在A2输入 “”&A1 然后复制A2&#xff0c;打开剪贴板&#xff0c;点击刚才复制的内容&#xff0c;就会在A2显示计算结果...

26元/月起!腾讯云一键自动搭建4核16G幻兽帕鲁服务器

腾讯云无需任何配置自动搭建幻兽帕鲁游戏联机服务器&#xff0c;游戏24小时在线&#xff0c;4核16G游戏联机服务器低至26元/月起&#xff0c;新手小白也能一键搭建属于自己的幻兽帕鲁游戏联机服务器&#xff01; 第一步&#xff1a;购买游戏联机服务器 购买入口&#xff1a;htt…...

【C++游戏开发-01】推箱子

C游戏开发 文章目录 C游戏开发[TOC](文章目录) 前言一、逻辑分析1.1地图实现1.2人物的移动1.2.1小人移动1.2.2其他移动 1.3墙壁的碰撞1.4箱子的推动1.4.1什么时候推箱子1.4.2什么情况可以推箱子 1.5胜利的判断1.6卡关的处理1.7关卡的切换 二、DEMO代码2.1游戏框架2.2各功能函数…...

【lesson26】学习MySQL事务前的基础知识

文章目录 CURD不加控制&#xff0c;会有什么问题&#xff1f;CURD满足什么属性&#xff0c;能解决上述问题&#xff1f;什么是事务&#xff1f;为什么会出现事务事务的版本支持 CURD不加控制&#xff0c;会有什么问题&#xff1f; CURD满足什么属性&#xff0c;能解决上述问题&…...

持续积累分享金融知识

持续积累分享金融知识 一、什么是两融余额&#xff1f;二、什么是量化&#xff1f;三、散户可以进行量化投资么&#xff1f; 一、什么是两融余额&#xff1f; 两融余额是指投资者在融资买入和融券卖出交易中&#xff0c;通过向券商借入资金或证券进行交易&#xff0c;并且在交…...

网络协议 UDP协议

网络协议 UDP协议 在之前的文章中有对UDP协议套接字的使用进行讲解&#xff0c;本文主要对UDP协议进行一些理论补充。 文章目录 网络协议 UDP协议1. 概念2. UDP协议格式2.1 数据报长度2.2 校验和/检验和2.2.1 CRC校验2.2.2 MD5算法 1. 概念 UDP&#xff0c;即User Datagram P…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

git: early EOF

macOS报错&#xff1a; Initialized empty Git repository in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core/.git/ remote: Enumerating objects: 2691797, done. remote: Counting objects: 100% (1760/1760), done. remote: Compressing objects: 100% (636/636…...

轻量级Docker管理工具Docker Switchboard

简介 什么是 Docker Switchboard &#xff1f; Docker Switchboard 是一个轻量级的 Web 应用程序&#xff0c;用于管理 Docker 容器。它提供了一个干净、用户友好的界面来启动、停止和监控主机上运行的容器&#xff0c;使其成为本地开发、家庭实验室或小型服务器设置的理想选择…...