(1)回溯算法团灭子集、组合、排列问题 -- 元素无重不可复选

news/2024/2/27 17:19:55

回溯算法团灭子集、组合、排列问题
根据元素是否重复和是否可复选,分为以下三种变体:
1、元素无重不可复选
2、元素有重不可复选
3、元素无重可复选

该篇给出第一种情况的代码,另外两种的实现见上方变体链接。


class NoRepeatAndSingle:"""元素无重不可复选"""def subsets(self, nums: List[int]) -> List[List[int]]:"""子集问题:param nums::return:"""self.res = []self.track = []self.s_backtrack(nums, 0)return self.resdef s_backtrack(self, nums, start):#  前序位置,每个节点的值都是⼀个⼦集self.res.append(self.track[:])for i in range(start, len(nums)):# 做选择self.track.append(nums[i])# 通过 start 参数控制树枝的遍历,避免产⽣重复的⼦集self.s_backtrack(nums, i+1)# 撤销选择self.track.pop()def combination(self, nums: List[int], k: int) -> List[List[int]]:"""组合问题:param nums::param k::return:"""self.res = []self.track = []self.c_backtrack(nums, 0, k)return self.resdef c_backtrack(self, nums, start, k):#  base caseif len(self.track) == k:self.res.append(self.track[:])returnfor i in range(start, len(nums)):# 做选择self.track.append(nums[i])# 通过 start 参数控制树枝的遍历,避免产⽣重复的⼦集self.c_backtrack(nums, i+1, k)# 撤销选择self.track.pop()def permute(self, nums: List[int]) -> List[List[int]]:"""排列问题:param nums::return:"""self.res = []self.track = []self.used = [False] * len(nums)self.p_backtrack(nums)return self.resdef p_backtrack(self, nums):#  base caseif len(self.track) == len(nums):self.res.append(self.track[:])returnfor i in range(0, len(nums)):# 已经存在 track 中的元素,不能重复选择if self.used[i]:continue# 做选择self.used[i] = Trueself.track.append(nums[i])# 通过 start 参数控制树枝的遍历,避免产⽣重复的⼦集self.p_backtrack(nums)# 撤销选择self.used[i] = Falseself.track.pop()

http://www.ppmy.cn/news/1092851.html

相关文章

vue3组件通信学习笔记

1、Prop 父组件 <template><div class"parent"><h1>我是父元素</h1><Child :msg"msg"></Child></div> </template><script setup> import Child from ./Child.vue let msg ref(我是父组件的数据…

使用Java分析器优化代码性能,解决OOM问题

有的时候博客内容会有变动&#xff0c;首发博客是最新的&#xff0c;其他博客地址可能会未同步,认准https://blog.zysicyj.top 首发博客地址 背景 最近我一直在做性能优化&#xff0c;对一个单机应用做性能优化。主要是涉及到解析和导入导出相关的业务。 大致说一下这个单机应用…

jenkins快速跑通helloworld任务

jenkins新建helloworld示例 左上角“新建任务” 输入名称&#xff0c;选择第一个创建&#xff1a; 可以选择众多执行脚本&#xff0c;这里选择shell&#xff1a; 随后弹出一个窗口&#xff0c;将下面脚本填入&#xff1a; #!/bin/bashecho start... for i in {1..10}doecho $i…

下载git

1.官网下载可能会有访问失败 2.用其他的镜像源下载 快 准 狠 CNPM Binaries Mirror

读SQL学习指南(第3版)笔记13_读后总结与感想兼导读

1. 基本信息 SQL学习指南(第3版) Learning SQL, Third Edition [美] 艾伦博利厄 &#xff08;Alan Beaulieu&#xff09; 人民邮电出版社,2022年4月出版 1.1. 读薄率 书籍总字数424千字&#xff0c;笔记总字数25969字。 读薄率25969424000≈6.13% 1.2. 读厚方向 SQL入门经…

阿里云服务器怎么退款?云服务器退款流程图

阿里云服务器如何退款&#xff1f;云服务器在哪申请退款&#xff1f;在用户中心订单管理中的退订管理中退款&#xff0c;阿里云百科分享阿里云服务器退款流程&#xff0c;包括申请退款入口、云服务器退款限制条件、退款多久到账等详细说明&#xff1a; 目录 阿里云服务器退款…

【Nginx23】Nginx学习:响应头与Map变量操作

Nginx学习&#xff1a;响应头与Map变量操作 响应头是非常重要的内容&#xff0c;浏览器或者客户端有很多东西可能都是根据响应头来进行判断操作的&#xff0c;比如说最典型的 Content-Type &#xff0c;之前我们也演示过&#xff0c;直接设置一个空的 types 然后指定默认的数据…

Docker的简介及安装

[shouce]http://shouce.jb51.net/docker_practice/栾一峰菜鸟教程参考文献 1 环境配置的难题 软件开发最大的麻烦事之一&#xff0c;就是环境配置。用户计算机的环境都不相同&#xff0c;你怎么知道自家的软件&#xff0c;能在那些机器跑起来&#xff1f; 用户必须保证两件事…

vue3项目,点击分页器,列表接口请求两次的问题

接手别人做的项目&#xff0c;出现了一个分页器bug&#xff0c;vue3element plus&#xff0c;记录一下。 点击分页器&#xff0c;却出现了调用两次列表接口的情况&#xff0c;并且第二次请求&#xff0c;分页器的pageNum自动变成1&#xff0c;这样就导致了分页器bug&#xff0…

网络通信深入解析:探索TCP/IP模型

http协议访问web 你知道在我们的网页浏览器的地址当中输入url&#xff0c;未必是如何呈现的吗&#xff1f; web浏览器根据地址栏中指定的url&#xff0c;从web服务器获取文件资源&#xff08;resource&#xff09;等信息&#xff0c;从而显示出web页面。web使用HTTP&#xff08…

git 配置

vi ~/.gitconfig 安装开源命令行对比工具 delta: https://github.com/dandavison/delta 详细设置delta&#xff1a;https://www.5axxw.com/wiki/content/xrx4vf [user]name xxemail xxxxxx.com[core]attributesfile ~/.gitattributespager deltaquotepath false[credentia…

Spring 6.0和SpringBoot 3.0新特性

目录 主要更新内容是以下几个&#xff1a; AOT编译 Spring Native GraalVM SpringBoot3生成二进制可执行文件底层流程 主要更新内容是以下几个&#xff1a; A Java 17 baselineSupport for Jakarta EE 10 with an EE 9 baselineSupport for generating native images with…

链表例题小总结:

链表&#xff1a; 第一种题型&#xff1a;双指针 力扣203&#xff1a;移除链表元素 力扣题目链接 题意&#xff1a;删除链表中等于给定值 val 的所有节点。示例 1&#xff1a; 输入&#xff1a;head [1,2,6,3,4,5,6], val 6 输出&#xff1a;[1,2,3,4,5]示例 2&#xff1…

K8s和Docker

Kubernetes&#xff08;简称为K8s&#xff09;和Docker是两个相关但又不同的技术。 一、Docker 1、Docker是一种容器化平台&#xff0c;用于将应用程序及其依赖项打包成可移植的容器。 2、Docker容器可以在任何支持Docker的操作系统上运行 好处&#xff1a;提供了一种轻量级…

机器学习笔记:node2vec(论文笔记:node2vec: Scalable Feature Learning for Networks)

2016 KDD 1 intro 利用graph上的节点相似性&#xff0c;对这些节点进行embedding 同质性&#xff1a;节点和其周围节点的embedding比较相似 蓝色节点和其周围的节点结构等价性 结构相近的点embedding相近 比如蓝色节点&#xff0c;都处于多个簇的连接处 2 随机游走 2.1 介绍…

测量网络性能的开源工具iperf3

iperf3是一个用于测量网络性能的开源工具。它可以通过在客户端和服务器之间进行数据传输来评估网络带宽、延迟、丢包率以及其他相关指标。 在使用iperf3进行网络性能测试时&#xff0c;通常需要在一台计算机上运行iperf3服务器&#xff0c;并在另一台计算机上运行iperf3客户端…

语音识别数据的采集方法:基本流程数据类型

“人工智能是一种模仿人类功能的产品。数据采集的方法需要针对特定的场景需求。”—–Mark Brayan (澳鹏CEO) 我们一直说&#xff0c;对于一个高质量的人工智能产品离不开高质量的训练数据。对于不同的人工智能我们需要不同的数据对其训练。要采集正确的数据去训练特定的模型才…

C++学习记录——삼십이 C++IO流

文章目录 1、C标准IO流2、C文件IO流1、二进制读写2、文本读写 3、stringstream 1、C标准IO流 C语言的printf和scanf无法很好的输入输出自定义类型&#xff0c;且还需要程序员自己确定类型&#xff0c;所以C就引入了输入流和输出流&#xff0c;是设备和内存之间的沟通。 其实io…

Spring Boot 集成 Redis

Spring-data-redis 在 Spring 中整合 Redis jedis : 采用的直连&#xff0c;多个线程操作的话&#xff0c;是不安全的&#xff0c;如果想要避免不安全的&#xff0c;使用 jedis pool 连接池 lettuce : 采用netty&#xff0c;实例可以再多个线程中进行共享&#xff0c;不存在…

ChatGPT Prompting开发实战(六)

一、编写清晰和有具体的指令&#xff08;instructions&#xff09;的prompt 要点描述&#xff1a; 使用包含少样本&#xff08;few-shot&#xff09;的prompt&#xff0c;让模型参考来输出答案。 prompt示例如下&#xff1a; prompt f""" Your task is to…
最新文章