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

leetcode77组合——经典回溯算法

本文主要讲解组合的要点与细节,以及回溯算法的解题步骤,按照步骤思考更方便理解 

c++和java代码如下,末尾

给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

 具体要点:

1. 首先,这道题的暴力解法是k层for循环,遍历所有的情况。但是这样子时间复杂度会很高。所以对于这类排列组合的问题,通常我们使用回溯算法来进行遍历,可以花一分钟参考回溯的前言概述。


2. 然后让我们来回顾一下回溯,回溯本质是一个树结构通常是由两个结构组成:for+递归。

        其中,for用来表示树的宽度,遍历每层的集合元素集,可以理解一个节点有多少个孩子,这个for循环就执行多少次。

        递归用来表示树的深度


3. 对于本题要求,我们需要先创建两个数组,一个用来存放最终的结果,一个用来存放过程中每次的结果

vector<vector<int>> res; //用来存放最终的结果
vector<int> temp; //用来存放过程中每次的结果

 4. 接着我们就可以考虑回溯算法的实现,具体包括两部分:for循环+递归

首先,我们来考虑递归,说到递归,就要思考递归三要素

  • 递归函数参数与返回值
  • 终止条件
  • 单层递归逻辑

返回值:由于我们是直接操作数组,不像二叉树一样需要返回节点,所以递归的返回值是void

参数:回溯算法中的递归参数较多,我们在写代码过程中慢慢添加

终止条件:也就是我们收集结果的条件,当我们的temp存放的数量等于k时,就需要收集结果了

单层递归逻辑:添加当前元素a到temp中——a向下递归——移除刚才添加的元素a

其次,让我们考虑一下for循环的细节

        for循环的起始值应该是什么呢?

        这个细节是回溯中重要的点,因为本题是“组合”,所以不需要顺序,即{1,2}和{2,1}是一个意思,只保留一个,所以下一层递归时,起始值就+1,从而达到去重的目的。

    void backtracing(int n, int k,vector<vector<int>>& res, vector<int> temp,int start) {//终止条件if (temp.size() == k) {//收集结果res.push_back(temp);return;}for (int i = start; i <= n; ++i) {temp.push_back(i);//添加当前元素backtracing(n, k, res, temp, i + 1);//相下递归,起始值+1temp.pop_back();//删除刚才添加的元素,实现回溯}return;}

以上就是回溯的整体逻辑,让我们总结一下重要的细节:

  • 递归的返回值
  • 递归的终止条件
  • for循环的起始值

在回溯过程中大家重点思考一下这几个细节点,有助于我们更好的实现代码

如果觉得我的讲解有一点帮助,十分感谢您的喜欢。

c++代码:

#include<bits/stdc++.h>
using namespace std;class Solution {
public:vector<vector<int>> combine(int n, int k) {//组合,不考虑顺序vector<vector<int>> res;vector<int> temp;backtracing(n, k, res, temp, 1);return res;}void backtracing(int n, int k,vector<vector<int>>& res, vector<int> temp,int start) {//终止条件if (temp.size() == k) {//收集结果res.push_back(temp);return;}for (int i = start; i <= n; ++i) {temp.push_back(i);//添加当前元素backtracing(n, k, res, temp, i + 1);//相下递归temp.pop_back();//删除刚才添加的元素,实现回溯}return;}};

java代码


class Solution {public List<List<Integer>> combine(int n, int k) {List<List<Integer>> res = new ArrayList<List<Integer>>();List<Integer> temp = new ArrayList<>();backtracking(n, k, res, temp, 1);return res;}public void backtracking(int n, int k, List<List<Integer>> res, List<Integer> temp, int start) {//终止条件if (temp.size() == k) {res.add(new ArrayList<>(temp));return;}for (int i = start; i <= n; i++) {temp.add(i);backtracking(n, k, res, temp, i + 1);temp.remove(temp.size() - 1);}return;}
}

相关文章:

leetcode77组合——经典回溯算法

本文主要讲解组合的要点与细节&#xff0c;以及回溯算法的解题步骤&#xff0c;按照步骤思考更方便理解 c和java代码如下&#xff0c;末尾 给定两个整数 n 和 k&#xff0c;返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 具体要点&#xff1a; …...

springcloud-alibba之FeignClient

代码地址&#xff1a;springcloud系列: springcloud 组件分析拆解 1.FeignClient的集成 springboot版本&#xff1a;3.1.5 springcloud组件版本&#xff1a;2022.0.4 nacos客户端的版本&#xff1a;2.3.2 1.引pom 这里引入了nacos和feginclient的版本 <dependency>…...

三、docker配置阿里云镜像仓库并配置docker代理

一、配置阿里云镜像仓库 1. 登录阿里云官网&#xff0c;并登录 https://www.aliyun.com/ 2. 点击产品 - 容器 - 容器与镜像服务ACR - 管理控制台 - 镜像工具 - 镜像加速器 二、配置docker代理 #1. 创建docker相关的systemd文件 mkdir -p /etc/systemd/system/docker.servic…...

【面向就业的Linux基础】从入门到熟练,探索Linux的秘密(十一)-git(3)

Git是目前最流行的版本控制系统之一&#xff0c;在现代软件开发中扮演着重要的角色。它能够有效地跟踪文件变化、协作开发&#xff0c;并存储项目的历史记录。本文的目的是向读者介绍Git的基本概念和工作原理&#xff0c;帮助初学者快速上手使用Git&#xff0c;并帮助有经验的开…...

全面解析 TypeScript 泛型的二三事

2024年了相信大家都已经在日常开发的过程中使用上了 TypeScript 了。TypeScript 增强了代码可靠性和可维护性&#xff0c;确保减少运行时错误并提高开发人员的工作效率。 TypeScript 通过类型声明 使得 javascript 拥有了强类型校验。而泛型的是类型声明中最重要的一环&#x…...

单/多线程--协程--异步爬虫

免责声明:本文仅做技术交流与学习... 目录 了解进程和线程 单个线程(主线程)在执行 多线程 线程池 协程(爬虫多用) 假异步:(同步) 真异步: 爬虫代码模版 异步-爬虫 同步效果--19秒 异步效果--7秒 了解进程和线程 ​ # --------------------> # ------> # …...

android pdf框架-11,查看图片

前10篇文章,9章关于pdf的,pdf解析后,里面也是有各种图片,于是利用pdf的view来展示图片,似乎也是个不错的想法. android手机中的图片查看功能,有的可以展示,有的不能.比如华为,荣耀对大体积的png是可以显示的,小米是不显示,只有缩略图. 一张png50m大,比如清明上河图,原图是tif…...

【CSS】深入浅出弹性布局

CSS的弹性布局&#xff08;Flexbox&#xff09;是一种用于在容器中沿着一维方向&#xff08;水平或垂直&#xff09;来布局、对齐和分配容器内项目空间的有效方式。它旨在提供一个更加有效的方式来布局、对齐和分配容器中项目的空间&#xff0c;即使它们的大小未知或是动态变化…...

医院挂号系统小程序的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;患者管理&#xff0c;医生管理&#xff0c;专家信息管理&#xff0c;科室管理&#xff0c;预约信息管理&#xff0c;系统管理 微信端账号功能包括&#xff1a;系统首页&#xff0c;专家信息&#xff0…...

广州外贸建站模板

Yamal外贸独立站wordpress主题 绿色的亚马尔Yamal外贸独立站wordpress模板&#xff0c;适用于外贸公司建独立站的wordpress主题。 https://www.jianzhanpress.com/?p7066 赛斯科Sesko-W外贸建站WP主题 适合机械设备生产厂家出海做外贸官网的wordpress主题&#xff0c;红橙色…...

KDP数据分析实战:从0到1完成数据实时采集处理到可视化

智领云自主研发的开源轻量级Kubernetes数据平台&#xff0c;即Kubernetes Data Platform (简称KDP)&#xff0c;能够为用户提供在Kubernetes上的一站式云原生数据集成与开发平台。在最新的v1.1.0版本中&#xff0c;用户可借助 KDP 平台上开箱即用的 Airflow、AirByte、Flink、K…...

【人工智能】-- 智能机器人

个人主页&#xff1a;欢迎来到 Papicatch的博客 课设专栏 &#xff1a;学生成绩管理系统 专业知识专栏&#xff1a; 专业知识 文章目录 &#x1f349;引言 &#x1f349;机器人介绍 &#x1f348;机器人硬件 &#x1f34d;机械结构 &#x1f34d;传感器 &#x1f34d;控…...

Android广播机制

简介 某个网络的IP范围是192.168.0.XXX&#xff0c;子网 掩码是255.255.255.0&#xff0c;那么这个网络的广播地址就是192.168.0.255。广播数据包会被发送到同一 网络上的所有端口&#xff0c;这样在该网络中的每台主机都将会收到这条广播。为了便于进行系统级别的消息通知&…...

SQL FOREIGN KEY

SQL FOREIGN KEY 简介 SQL(Structured Query Language)是用于管理关系数据库管理系统(RDBMS)的标准编程语言。在SQL中,FOREIGN KEY是一个重要的概念,用于建立和维护数据库中不同表之间的关系。本文将详细介绍SQL FOREIGN KEY的概念、用途、以及如何在SQL中实现和使用FO…...

绘唐3最新版本哪里下载

绘唐3最新版本哪里下载 绘唐最新版本下载地址 推文视频创作设计是一种通过视频和文字的形式来进行推广的方式&#xff0c;可以通过一些专业的工具来进行制作。 以下是一些常用的小说推文视频创作设计工具&#xff1a; 视频剪辑软件&#xff1a;如Adobe Premiere Pro、Fina…...

[ES6] 箭头函数

JavaScript 是一种广泛使用的编程语言&#xff0c;随着其发展和演变&#xff0c;引入了很多新的特性来提高代码的可读性和开发效率。其中一个重要的特性就是 ES6&#xff08;ECMAScript 2015&#xff09;中引入的箭头函数&#xff08;Arrow Function&#xff09;。箭头函数不仅…...

BiLSTM模型实现

# 本段代码构建类BiLSTM, 完成初始化和网络结构的搭建 # 总共3层: 词嵌入层, 双向LSTM层, 全连接线性层 # 本段代码构建类BiLSTM, 完成初始化和网络结构的搭建 # 总共3层: 词嵌入层, 双向LSTM层, 全连接线性层 import torch import torch.nn as nn# 本函数实现将中文文本映射为…...

linux内核源码学习所需基础

1.面向对象的思想&#xff0c;尤其是oopc的实现方式。 2.设计模式。 这两点需要内核源码学习者不仅要会c和汇编&#xff0c;还要接触一门面向对象的语言&#xff0c;比如c&#xff0b;&#xff0b;/java/python等等任意一门都行&#xff0c;起码要了解面向对象的思想。 另外li…...

Java并发编程-AQS详解及案例实战(上篇)

文章目录 AQS概述AQS 的核心概念AQS 的工作原理AQS 的灵活性使用场景使用指南使用示例AQS的本质:为啥叫做异步队列同步器AQS的核心机制“异步队列”的含义“同步器”的含义总结加锁失败的时候如何借助AQS异步入队阻塞等待AQS的锁队列加锁失败时的处理流程异步入队的机制总结Ree…...

第11章 规划过程组(二)(11.8排列活动顺序)

第11章 规划过程组&#xff08;二&#xff09;11.8排列活动顺序&#xff0c;在第三版教材第391页&#xff1b; 文字图片音频方式 第一个知识点&#xff1a;主要输出 1、项目进度网络图 如图11-20 项目进度网络图示例 带有多个紧前活动的活动代表路径汇聚&#xff0c;而带有…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

【 java 虚拟机知识 第一篇 】

目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...

PHP 8.5 即将发布:管道操作符、强力调试

前不久&#xff0c;PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5&#xff01;作为 PHP 语言的又一次重要迭代&#xff0c;PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是&#xff0c;借助强大的本地开发环境 ServBay&am…...

论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing

Muffin 论文 现有方法 CRADLE 和 LEMON&#xff0c;依赖模型推理阶段输出进行差分测试&#xff0c;但在训练阶段是不可行的&#xff0c;因为训练阶段直到最后才有固定输出&#xff0c;中间过程是不断变化的。API 库覆盖低&#xff0c;因为各个 API 都是在各种具体场景下使用。…...

elementUI点击浏览table所选行数据查看文档

项目场景&#xff1a; table按照要求特定的数据变成按钮可以点击 解决方案&#xff1a; <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...