回溯算法解决排列组合及子集问题
| 216. 组合总和 III |
| 39. 组合总和 |
| 40. 组合总和 II |
| 46. 全排列 |
| 47. 全排列 II |
| 77. 组合 |
| 78. 子集 |
| 90. 子集 II |
以上是力扣设计相关问题的题目。排列组合还是子集问题无非就是从序列 nums 中以给定规则取若干元素,主要有以下几类:
- 元素无重不可复选,即
nums中的元素都是唯一的,每个元素最多只能被使用一次,这也是最基本的形式。 - 元素可重不可复选,即
nums中的元素可以存在重复,每个元素最多只能被使用一次。 - 元素无重可复选,即
nums中的元素都是唯一的,每个元素可以被使用若干次。
以组合为例:
1.如果输入
nums = [2,3,6,7],和为 7 的组合应该只有[7]2.如果输入
nums = [2,5,2,1,2],和为 7 的组合应该有两种[2,2,2,1]和[5,2]3.如果输入
nums = [2,3,6,7],和为 7 的组合应该有两种[2,2,3]和[7]
上面用组合问题举的例子,但排列、组合、子集问题都可以有这三种基本形式,所以共有 9 种变化。
除此之外,题目也可以再添加各种限制条件,比如让你求和为 target 且元素个数为 k 的组合,那这么一来又可以衍生出一堆变体,所以一般笔试很喜欢出这种题。
但无论怎么变化,其本质就是穷举所有解,而这些解呈现树形结构,使用回溯算法框架再稍微修改一些细节即可把这些问题一网打尽。
回溯算法框架代码如下:
import java.util.ArrayList;
import java.util.List;public class BacktrackExample {private List<List<Object>> result = new ArrayList<>();public void backtrack(List<Object> path, List<Object> choices) {if (满足结束条件(path)) {result.add(new ArrayList<>(path));return;}for (Object choice : choices) {// 做选择path.add(choice);// 递归backtrack(path, choices);// 撤销选择path.remove(path.size() - 1);}}private boolean 满足结束条件(List<Object> path) {// 这里实现满足结束条件的逻辑return false; // 示例返回,替换为实际逻辑}public List<List<Object>> getResult() {return result;}}
问题一:当元素无重不可复选时,即 nums 中的元素都是唯一的,每个元素最多只能被使用一次:
// 组合/子集问题回溯算法框架
void backtrack(int[] nums, int start) {// 回溯算法标准框架for (int i = start; i < nums.length; i++) {// 做选择track.addLast(nums[i]);// 注意参数backtrack(nums, i + 1);// 撤销选择track.removeLast();}
}// 排列问题回溯算法框架
void backtrack(int[] nums) {for (int i = 0; i < nums.length; i++) {// 剪枝逻辑if (used[i]) {continue;}// 做选择used[i] = true;track.addLast(nums[i]);backtrack(nums);// 撤销选择track.removeLast();used[i] = false;}
}
问题二:元素可重不可复选,即 nums 中的元素可以存在重复,每个元素最多只能被使用一次,其关键在于排序和剪枝
Arrays.sort(nums);
// 组合/子集问题回溯算法框架
void backtrack(int[] nums, int start) {// 回溯算法标准框架for (int i = start; i < nums.length; i++) {// 剪枝逻辑,跳过值相同的相邻树枝if (i > start && nums[i] == nums[i - 1]) {continue;}// 做选择track.addLast(nums[i]);// 注意参数backtrack(nums, i + 1);// 撤销选择track.removeLast();}
}Arrays.sort(nums);
// 排列问题回溯算法框架
void backtrack(int[] nums) {for (int i = 0; i < nums.length; i++) {// 剪枝逻辑if (used[i]) {continue;}// 剪枝逻辑,固定相同的元素在排列中的相对位置if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {continue;}// 做选择used[i] = true;track.addLast(nums[i]);backtrack(nums);// 撤销选择track.removeLast();used[i] = false;}
}
问题三:元素无重可复选,即 nums 中的元素都是唯一的,每个元素可以被使用若干次,只要删掉去重逻辑即可:
// 组合/子集问题回溯算法框架
void backtrack(int[] nums, int start) {// 回溯算法标准框架for (int i = start; i < nums.length; i++) {// 做选择track.addLast(nums[i]);// 注意参数backtrack(nums, i);// 撤销选择track.removeLast();}
}// 排列问题回溯算法框架
void backtrack(int[] nums) {for (int i = 0; i < nums.length; i++) {// 做选择track.addLast(nums[i]);backtrack(nums);// 撤销选择track.removeLast();}
}
只要从树的角度思考,这些问题看似复杂多变,实则改改 base case 就能解决。只要熟悉了该框架,再细致了解一下细节问题,相信排列组合子集问题都不是问题。
相关文章:
回溯算法解决排列组合及子集问题
216. 组合总和 III39. 组合总和40. 组合总和 II46. 全排列47. 全排列 II77. 组合 78. 子集 90. 子集 II 以上是力扣设计相关问题的题目。排列组合还是子集问题无非就是从序列 nums 中以给定规则取若干元素,主要有以下几类: 元素无重不可复选࿰…...
Unity中Mesh多种网格绘制模式使用方法参考
Unity中MeshFilter中的Mesh默认情况下使用MeshTopology.Trigangles类型绘制网格,就是通常的绘制三角形网格,实际上Mesh有五种绘制模式,对应MeshTopology的枚举,分别是 Triangles网格由三角形构成。Quads网格由四边形构成。Lines网…...
【Spring Security】基于SpringBoot3.3.4版本②如何配置免鉴权Path
基于Spring Boot 3.3.4,详细说明Spring Security 6.3.3的使用 摘要本地开发环境说明SecurityFilterChain介绍application.ymlWen3SecurityProperties.java修改DemoWen3Security修改SecurityFilterChainIgnoredPathController.javaIgnoredPathController2.java启动工程测试测试…...
信息学奥赛复赛复习11-CSP-J2020-04方格取数-动态规划、斐波那契数列、最优子结构、重叠子问题、无后效性
PDF文档回复:20241004 1 P7074 [CSP-J2020] 方格取数 [题目描述] 设有 nm 的方格图,每个方格中都有一个整数。现有一只小熊,想从图的左上角走到右下角,每一步只能向上、向下或向右走一格,并且不能重复经过已经走过的方格&#x…...
Hive数仓操作(十二)
一、Hive 中的行列转换 1. 行转列: collect_list() collect_list() 函数用于将一个列中的数据收集成一个数组。 示例数据文件 假设有一个名为 orders.txt 的文件,内容如下: 1,101 1,101 1,103 2,104 2,105导入数据到 Hive 表 首先&…...
计算机毕业设计 基于SpringBoot和Vue的课程教学平台的设计与实现 Java实战项目 附源码+文档+视频讲解
博主介绍:✌从事软件开发10年之余,专注于Java技术领域、Python人工智能及数据挖掘、小程序项目开发和Android项目开发等。CSDN、掘金、华为云、InfoQ、阿里云等平台优质作者✌ 🍅文末获取源码联系🍅 👇🏻 精…...
有状态(Session) VS 无状态(Token)
目录 概念 JWT Token在项目中使用 概念 有状态和无状态服务是两种不同的服务架构,两者的不同之处在于对于服务状态的处理。 1、有状态服务 是指程序在执行过程中生成的中间数据,服务器端一般都要保存请求的相关信息,每个请求可以默认地使…...
天坑!Spark+Hive+Paimon+Dolphinscheduler
背景: 数据中台项目使用Spark+Hive+Paimon做湖仓底层,调度任务使用的是基于Dolphinscheduler进行二开。在做离线脚本任务开发时,在Paimon库下执行非查询类SQL报错。 INSERT报错 DELETE报错 现状: 原始逻辑为数据中台中选择的Paimon数据源,实际上在Dolphinscheduler中是…...
JAVA——IO框架
目录 一、框架 二、导入框架步骤 三、测试 一、框架 框架就是为了解决某类问题,编写的一套类、接口等。大多数框架都是第三方研发的 好处: 在框架的基础上开发,提高开发效率 框架的形式:一般是把类、接口编译成class形式,再…...
项目管理系统如何实现项目申报流程自动化?
传统的项目申报流程往往繁琐复杂,涉及众多环节和部门间的协作,不仅耗时费力,还容易因人为疏忽而导致错误或延误。随着信息技术的飞速发展,项目管理系统的出现为项目申报流程的自动化提供了可能,极大地提升了申报效率和…...
ndb9300public-ndb2excel简介
1 引言 ndb9300是一个自己定义的机载导航数据库劳作(不敢称为项目)代号,其中3表示是第3种数据库。 多年前,对在役民航客机中的某型机载导航数据库的二进制文件进行分析,弄明白它的数据结构后做了几个工具,…...
C++:const成员
const修饰成员变量,要在初始化列表中进行初始化。 const修饰成员函数,要放在函数后,称为常函数。常函数不能修改普通成员变量。 const修饰的对象,称为常对象。常对象不能修改普通成员变量,只能读取。 常对象只能使用…...
基于ROS的激光雷达点云物体检测
环境 RTX 2060(后面关于算力) ubuntu 18.04 ROS melodic (ubuntu 18.04安装ROS melodic可以参看我这篇文章ubuntu 18.04安装ROS系统) CUDA 10.0 cudnn 7.6.5 caffe cmake 3.18.0(不能低于3.12.2) opencv 3…...
大模型训练环境搭建
硬件资源说明 本教程基于GPU 3090的服务器 资源类型 型号 核心指标 CPU Intel(R) Xeon(R) Bronze 3204 CPU 1.90GHz 12核 内存 / 125Gi GPU NVIDIA GeForce RTX 3090 24G显存 注意:接下来的部分命令需要使用科学上网,需要事先配置好。 安…...
使用Java调用GeoTools实现全球国家矢量数据入库实战
目录 前言 一、相关数据介绍 1、无空间参考的数据 2、有空间参考的数据 3、空间信息表物理模型 二、全球国家空间数据入库 1、后台实体类图 2、后台实体对象关键代码 三、时空数据入库实践 1、读取无空间参考数据 2、入库成果及注意事项 四、总结 前言 在当今世界&…...
计算机毕业设计 基于Python的广东旅游数据分析系统的设计与实现 Python+Django+Vue Python爬虫 附源码 讲解 文档
🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点…...
Springboo通过http请求下载文件到服务器
这个方法将直接处理从URL下载数据并将其保存到文件的整个过程。下面是一个这样的方法示例: import java.io.FileOutputStream; import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.net.HttpURLConnection…...
使用CSS实现酷炫加载
使用CSS实现酷炫加载 效果展示 整体页面布局 <div class"container"></div>使用JavaScript添加loading加载动画的元素 document.addEventListener("DOMContentLoaded", () > {let container document.querySelector(".container&q…...
【STM32-HAL库】AHT10温湿度传感器使用(STM32F407ZGT6配置i2c)(附带工程下载连接)
一、温湿度传感器: 温湿度传感器是一种能够检测环境中的温度和湿度,并将其转化为电信号输出的装置。它在智能家居、工业自动化、气象监测、农业等领域有着广泛的应用。 原理: 温湿度传感器通常基于不同的物理原理,以下是一些常见…...
深入理解网络通信: 长连接、短连接与WebSocket
在现代网络应用开发中,选择合适的通信方式对于应用的性能、效率和用户体验至关重要。本文将深入探讨三种常见的网络通信方式:长连接、短连接和WebSocket,分析它们的特点、区别以及适用场景。 1. 短连接 © ivwdcwso (ID: u012172506) 1.1 定义 短连接是指客户端和服务器…...
Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误
HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误,它们的含义、原因和解决方法都有显著区别。以下是详细对比: 1. HTTP 406 (Not Acceptable) 含义: 客户端请求的内容类型与服务器支持的内容类型不匹…...
ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
Rust 异步编程
Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...
深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
Spring是如何解决Bean的循环依赖:三级缓存机制
1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间互相持有对方引用,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...
python爬虫——气象数据爬取
一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用: 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests:发送 …...
Oracle11g安装包
Oracle 11g安装包 适用于windows系统,64位 下载路径 oracle 11g 安装包...
十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建
【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...
[USACO23FEB] Bakery S
题目描述 Bessie 开了一家面包店! 在她的面包店里,Bessie 有一个烤箱,可以在 t C t_C tC 的时间内生产一块饼干或在 t M t_M tM 单位时间内生产一块松糕。 ( 1 ≤ t C , t M ≤ 10 9 ) (1 \le t_C,t_M \le 10^9) (1≤tC,tM≤109)。由于空间…...
