07、JS实现：用回溯法实现数组全排列的算法(一步一步剖析，很详细)

回溯法实现数组全排列的算法

  • Ⅰ、回溯法实现数组全排列：
    • 1、题目描述：
    • 2、解题思路：
    • 3、实现代码：
  • Ⅱ、小结：

Ⅰ、回溯法实现数组全排列：

1、题目描述：

给定⼀个 没有重复 数字的序列，返回其所有可能的全排列。
示例:
输⼊: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

2、解题思路：

以 [1,2,3] 为例，根据回溯思想，我们的逻辑是：
先从 [1,2,3] 选取⼀个数。
然后继续从 [1,2,3] 选取⼀个数，并且这个数不能是已经选取过的数。
重复这个过程直到选取的数字个数达到了 3。


可能存在的问题：
其一、如何确保这个数不能是已经选取过的数？
答：我们可以直接在已经选取的数字中线性查找，也可以将已经选取的数字中放到 hashset 中，这样就可以在
O(1)的时间来判断是否已经被选取了，只不过需要额外的空间;

3、实现代码：

其一、代码为：


// 此时的 list 是空数组、tempList 是空数组、nums 是没有重复数字的数组;
const backtrack = (list, tempList, nums) => {if (tempList.length === nums.length) return list.push([...tempList])for (let i = 0; i < nums.length; i++) {// 此时 continue 的作用：若 if() 满足条件，则会跳出本次的 for 循环;if (tempList.includes(nums[i])) continuetempList.push(nums[i])backtrack(list, tempList, nums)tempList.pop()}
}const permute = (nums) => {const list = []backtrack(list, [], nums)return list
}// 此时的输出结果为：[ [ 1, 2, 3 ], [ 1, 3, 2 ], [ 2, 1, 3 ], [ 2, 3, 1 ], [ 3, 1, 2 ], [ 3, 2, 1 ] ];
permute([1, 2, 3])
执行  backtrack(list, [], nums)  函数后代码执行的过程(即：执行 backtrack([], [], [1,2,3]) 函数)：注意：里面涉及多个循环嵌套递归，每次递归的出口为 tempList.length === nums.length，循环的出口为 for() 循环结束;第一层循环，在 i=0 的情况下：if (tempList.includes(nums[i])) continue 的判断不成功;执行 tempList.push(nums[0]) 代码后，tempList 数组为 [1];backtrack(list, tempList, nums) 执行代码为：backtrack([], [1], [1,2,3])第二层循环，在 i=0 的情况下：if (tempList.includes(nums[i])) continue 的判断成功，因此直接跳出此次的 for() 循环的过程;第二层循环，在 i=1 的情况下：if (tempList.includes(nums[i])) continue 的判断不成功;执行 tempList.push(nums[1]) 代码后，tempList 数组为 [1,2];backtrack(list, tempList, nums) 执行代码为：backtrack([], [1,2], [1,2,3])第三层循环，在 i=0 的情况下：if (tempList.includes(nums[i])) continue 的判断成功，因此直接跳出此次的 for() 循环的过程;第三层循环，在 i=1 的情况下：if (tempList.includes(nums[i])) continue 的判断成功，因此直接跳出此次的 for() 循环的过程;第三层循环，在 i=2 的情况下：if (tempList.includes(nums[i])) continue 的判断不成功;执行 tempList.push(nums[2]) 代码后，tempList 数组为 [1,2,3];backtrack(list, tempList, nums) 执行代码为：backtrack([], [1,2,3], [1,2,3])if (tempList.length === nums.length) return list.push([...tempList])，list 的数组为[[1,2,3]];执行 tempList.pop() 代码后，tempList 数组为 [1,2];执行 tempList.pop() 代码后，tempList 数组为 [1];第二层循环，在 i=2 的情况下：if (tempList.includes(nums[i])) continue 的判断不成功;执行 tempList.push(nums[2]) 代码后，tempList 数组为 [1,3];backtrack(list, tempList, nums) 执行代码为：backtrack([[1,2,3]], [1,3], [1,2,3])第三层循环，在 i=0 的情况下：if (tempList.includes(nums[i])) continue 的判断成功，因此直接跳出此次的 for() 循环的过程;第三层循环，在 i=1 的情况下：if (tempList.includes(nums[i])) continue 的判断不成功;执行 tempList.push(nums[1]) 代码后，tempList 数组为 [1,3,2];backtrack(list, tempList, nums) 执行代码为：backtrack([[1,2,3]], [1,3,2], [1,2,3])if (tempList.length === nums.length) return list.push([...tempList])，list 的数组为[[1,2,3],[1,3,2]];执行 tempList.pop() 代码后，tempList 数组为 [1,3];第三层循环，在 i=2 的情况下：if (tempList.includes(nums[i])) continue 的判断成功，因此直接跳出此次的 for() 循环的过程;			执行 tempList.pop() 代码后，tempList 数组为 [1];执行 tempList.pop() 代码后，tempList 数组为 [];第一层循环，在 i=1 的情况下：if (tempList.includes(nums[i])) continue 的判断不成功;执行 tempList.push(nums[1]) 代码后，tempList 数组为 [2];backtrack(list, tempList, nums) 执行代码为：backtrack([[1,2,3],[1,3,2]], [2], [1,2,3])第二层循环，在 i=0 的情况下：if (tempList.includes(nums[i])) continue 的判断不成功;执行 tempList.push(nums[0]) 代码后，tempList 数组为 [2,1];backtrack(list, tempList, nums) 执行代码为：backtrack([[1,2,3],[1,3,2]], [2,1], [1,2,3])第三层循环，在 i=0 的情况下：if (tempList.includes(nums[i])) continue 的判断成功，因此直接跳出此次的 for() 循环的过程;第三层循环，在 i=1 的情况下：if (tempList.includes(nums[i])) continue 的判断成功，因此直接跳出此次的 for() 循环的过程;第三层循环，在 i=2 的情况下：if (tempList.includes(nums[i])) continue 的判断不成功;执行 tempList.push(nums[2]) 代码后，tempList 数组为 [2,1,3];backtrack(list, tempList, nums) 执行代码为：backtrack([[1,2,3],[1,3,2]], [2,1,3], [1,2,3])if (tempList.length === nums.length) return list.push([...tempList])，list 的数组为[[1,2,3],[1,3,2],[2,1,3]];执行 tempList.pop() 代码后，tempList 数组为 [2,1];执行 tempList.pop() 代码后，tempList 数组为 [2];第二层循环，在 i=1 的情况下：if (tempList.includes(nums[i])) continue 的判断成功，因此直接跳出此次的 for() 循环的过程;第二层循环，在 i=2 的情况下：if (tempList.includes(nums[i])) continue 的判断不成功;执行 tempList.push(nums[2]) 代码后，tempList 数组为 [2,3];backtrack(list, tempList, nums) 执行代码为：backtrack([[1,2,3],[1,3,2],[2,1,3]], [2,3], [1,2,3])第三层循环，在 i=0 的情况下：if (tempList.includes(nums[i])) continue 的判断不成功;执行 tempList.push(nums[0]) 代码后，tempList 数组为 [2,3,1];backtrack(list, tempList, nums) 执行代码为：backtrack([[1,2,3],[1,3,2],[2,1,3]], [2,3,1], [1,2,3])if (tempList.length === nums.length) return list.push([...tempList])，list 的数组为[[1,2,3],[1,3,2],[2,1,3],[2,3,1]];执行 tempList.pop() 代码后，tempList 数组为 [2,3];第三层循环，在 i=1 的情况下：if (tempList.includes(nums[i])) continue 的判断成功，因此直接跳出此次的 for() 循环的过程;第三层循环，在 i=2 的情况下：if (tempList.includes(nums[i])) continue 的判断成功，因此直接跳出此次的 for() 循环的过程;			执行 tempList.pop() 代码后，tempList 数组为 [2];执行 tempList.pop() 代码后，tempList 数组为 [];第一层循环，在 i=2 的情况下：if (tempList.includes(nums[i])) continue 的判断不成功;执行 tempList.push(nums[2]) 代码后，tempList 数组为 [3];backtrack(list, tempList, nums) 执行代码为：backtrack([[1,2,3],[1,3,2],[2,1,3],[2,3,1]], [3], [1,2,3])第二层循环，在 i=0 的情况下：if (tempList.includes(nums[i])) continue 的判断不成功;执行 tempList.push(nums[0]) 代码后，tempList 数组为 [3,1];backtrack(list, tempList, nums) 执行代码为：backtrack([[1,2,3],[1,3,2],[2,1,3],[2,3,1]], [3,1], [1,2,3])第三层循环，在 i=0 的情况下：if (tempList.includes(nums[i])) continue 的判断成功，因此直接跳出此次的 for() 循环的过程;第三层循环，在 i=1 的情况下：if (tempList.includes(nums[i])) continue 的判断不成功;执行 tempList.push(nums[1]) 代码后，tempList 数组为 [3,1,2];backtrack(list, tempList, nums) 执行代码为：backtrack([[1,2,3],[1,3,2],[2,1,3],[2,3,1]], [3,1,2], [1,2,3])if (tempList.length === nums.length) return list.push([...tempList])，list 的数组为[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2]];执行 tempList.pop() 代码后，tempList 数组为 [3,1];第三层循环，在 i=2 的情况下：if (tempList.includes(nums[i])) continue 的判断成功，因此直接跳出此次的 for() 循环的过程;执行 tempList.pop() 代码后，tempList 数组为 [3];第二层循环，在 i=1 的情况下：if (tempList.includes(nums[i])) continue 的判断不成功;执行 tempList.push(nums[1]) 代码后，tempList 数组为 [3,2];backtrack(list, tempList, nums) 执行代码为：backtrack([[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2]], [3,2], [1,2,3])第三层循环，在 i=0 的情况下：if (tempList.includes(nums[i])) continue 的判断不成功;执行 tempList.push(nums[0]) 代码后，tempList 数组为 [3,2,1];backtrack(list, tempList, nums) 执行代码为：backtrack([[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2]], [3,2,1], [1,2,3])if (tempList.length === nums.length) return list.push([...tempList])，list 的数组为[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]];执行 tempList.pop() 代码后，tempList 数组为 [3,2];第三层循环，在 i=1 的情况下：if (tempList.includes(nums[i])) continue 的判断成功，因此直接跳出此次的 for() 循环的过程;第三层循环，在 i=2 的情况下：if (tempList.includes(nums[i])) continue 的判断成功，因此直接跳出此次的 for() 循环的过程;			执行 tempList.pop() 代码后，tempList 数组为 [3];第二层循环，在 i=2 的情况下：if (tempList.includes(nums[i])) continue 的判断成功，因此直接跳出此次的 for() 循环的过程;执行 tempList.pop() 代码后，tempList 数组为 [];因此，最后 list 的输出结果为：[ [ 1, 2, 3 ], [ 1, 3, 2 ], [ 2, 1, 3 ], [ 2, 3, 1 ], [ 3, 1, 2 ], [ 3, 2, 1 ] ],
而 tempList 的输出结果为：[];

其二、截图为：

在这里插入图片描述

Ⅱ、小结：

其一、哪里有不对或不合适的地方，还请大佬们多多指点和交流！
其二、若有转发或引用本文章内容，请注明本博客地址(直接点击下面 url 跳转) https://blog.csdn.net/weixin_43405300,创作不易，且行且珍惜！
其三、有兴趣的话，可以多多关注这个专栏(Vue(Vue2+Vue3)面试必备专栏)(直接点击下面 url 跳转)：https://blog.csdn.net/weixin_43405300/category_11525646.html?spm=1001.2014.3001.5482

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/288023.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Kimi 200万字爆火，通义加码1000万，阿里笑而不语

Kimi 200万字爆火，通义加码1000万，阿里笑而不语

关注卢松松&#xff0c;会经常给你分享一些我的经验和观点。 我怎么感觉Kimi是一个“网红”产品呢?在没有任何预兆情况下&#xff0c;国产AI大模型Kimi突然爆火&#xff0c;最近我在很多平台上看到了Kimi的广告&#xff0c;感觉到处都在吹这个产品。 看见上面的新闻了吧&a…
阅读更多...
使用Spark单机版环境

使用Spark单机版环境

在Spark单机版环境中&#xff0c;可通过多种方式进行实战操作。首先&#xff0c;可使用特定算法或数学软件计算圆周率π&#xff0c;并通过SparkPi工具验证结果。其次&#xff0c;在交互式Scala版或Python版Spark Shell中&#xff0c;可以进行简单的计算、打印九九表等操作&…
阅读更多...
VRAY渲染设置大神参数（建议收藏）

VRAY渲染设置大神参数（建议收藏）

3dmax效果图云渲染平台——渲染100以3ds Max 2024、VR 6.2、CR 11.2等最新版本为基础&#xff0c;兼容fp、acescg等常用插件&#xff0c;同时LUT滤镜等参数也得到了同步支持。注册填邀请码【7788】可领30元礼包和免费渲染券哦~ 公用&#xff1a;输出大小&#xff1a;一般小图50…
阅读更多...
JavaScript进阶5之垃圾回收（计算机组成、解释与编译、JavaScript引擎、垃圾回收、内存管理）、运行机制（浏览器进程分类、浏览器事件循环）

JavaScript进阶5之垃圾回收（计算机组成、解释与编译、JavaScript引擎、垃圾回收、内存管理）、运行机制（浏览器进程分类、浏览器事件循环）

垃圾回收&运行机制 垃圾回收计算机组成解释与编译JavaScript引擎V8引擎 垃圾回收引用计数法标记清除&#xff08;mark-sweep&#xff09;算法 内存管理新生代 运行机制浏览器进程分类&#xff1a;浏览器事件循环宏任务微任务整体流程浏览器事件循环案例一案例二 垃圾回收 …
阅读更多...
SpringBoot中处理校验逻辑的两种方式：Hibernate Validator+全局异常处理

SpringBoot中处理校验逻辑的两种方式：Hibernate Validator+全局异常处理

最近正在开发一个校园管理系统&#xff0c;需要对请求参数进行校验&#xff0c;比如说非空啊、长度限制啊等等&#xff0c;可选的解决方案有两种&#xff1a; 一种是用 Hibernate Validator 来处理一种是用全局异常来处理 两种方式&#xff0c;我们一一来实践体验一下。 一、…
阅读更多...
Oracle Data Guard部署

Oracle Data Guard部署

Oracle的主备DG搭建 1. 修改主机名,同步时间 主库IP&#xff1a;192.168.100.137 备库IP&#xff1a;192.168.100.138配置主机名(主库) Hostname zygjpdb vim /etc/hosts 192.168.100.137 zygjpdb 192.168.100.138 zygjsdbvim /etc/sysconfig/network HOSTNAMEzygjpdb ------…
阅读更多...
TransformControls 是 Three.js 中的一个类，用于在网页中进行 3D 场景中物体的交互式操作。

TransformControls 是 Three.js 中的一个类，用于在网页中进行 3D 场景中物体的交互式操作。

demo案例 TransformControls 是 Three.js 中的一个类&#xff0c;用于在网页中进行 3D 场景中物体的交互式操作。让我们来详细讲解它的输入参数、输出、属性和方法&#xff1a; 输入参数&#xff1a; TransformControls 构造函数通常接受两个参数&#xff1a; camera&#…
阅读更多...
YAPI接口自动鉴权功能部署详解

YAPI接口自动鉴权功能部署详解

安装准备 以下操作&#xff0c;默认要求自己部署过yapi&#xff0c;最好是部署过yapi二次开发环境。 无论是选择在线安装或者是本地安装&#xff0c;都需要安装client工具。 1、yapi-cli&#xff1a;npm install yapi-cli –g&#xff0c; 2、安装后将文件夹nodejs/node_gl…
阅读更多...
JavaScript 打印教程（第二部分）设置编码

JavaScript 打印教程（第二部分）设置编码

JavaScript 打印教程&#xff08;第二部分&#xff09;设置编码 在进行文本打印时&#xff0c;尤其是涉及到中文或其他特殊字符时&#xff0c;正确的编码设置是非常重要的。不同的打印机支持不同的指令集&#xff0c;因此了解并使用适合您打印机的指令集是关键。本篇教程继续使…
阅读更多...
使用 python 拆分 excel 文件

使用 python 拆分 excel 文件

文章目录 1、安装虚拟环境&#xff08;在特定文件夹内&#xff09;2、脚本 split.sh3、运行脚本&#xff08;在特定文件夹内&#xff09;4、结果 1、安装虚拟环境&#xff08;在特定文件夹内&#xff09; brew install python3 xcode-select --install python3 -m venv my_pan…
阅读更多...
【Python】Selenium自动化测试框架

【Python】Selenium自动化测试框架

设计思路 本文整理归纳以往的工作中用到的东西&#xff0c;现汇总成基础测试框架提供分享。 框架采用python3 selenium3 PO yaml ddt unittest等技术编写成基础测试框架&#xff0c;能适应日常测试工作需要。 1、使用Page Object模式将页面定位和业务操作分开&#xff0…
阅读更多...
【蓝牙协议栈】【SMP】安全管理协议

【蓝牙协议栈】【SMP】安全管理协议

1. SMP概念 SMP&#xff08;Security Manager Protocol&#xff09;即安全管理协议。SMP 是蓝牙用来进行安全管理的&#xff0c;其定义了配对和 Key&#xff08;可以理解成密钥&#xff09;的分发过程的实现&#xff0c;以及用于 实现这些方法的协议和工具。SMP 的内容主要是配…
阅读更多...
探索网络分析：图论算法介绍及其如何用于地理空间分析

探索网络分析：图论算法介绍及其如何用于地理空间分析

网络分析简介 出售真空吸尘器的挨家挨户的推销员列出了一个潜在客户，分布在邻近他的几个城市中。他想离开家，参观每个潜在客户，然后返回家园。他可以采取的最短、最有效的路线是什么？ 这种情况被称为旅行推销员问题，它可能是优化中研究最深入的问题（旅行推销员问题，2023…
阅读更多...
【Unity】调整Player Settings的Resolution设置无效

【Unity】调整Player Settings的Resolution设置无效

【背景】 Build时修改了Player Settings下的Resolution设置&#xff0c;但是再次Building时仍然不生效。 【分析】 明显是沿用了之前的分辨率设定&#xff0c;所以盲猜解决办法是Build相关的缓存文件&#xff0c;或者修改打包名称。 【解决】 实测修改版本号无效&#xf…
阅读更多...
推特社交机器人分类

推特社交机器人分类

机器人有不同的种类。 cresci-17数据集中的三种不同的机器人类:传统垃圾机器人、社交垃圾机器人和假追随者。 传统的垃圾邮件机器人会生成大量推广产品的内容&#xff0c;并且可以通过频繁使用的形容词来检测; 社交垃圾邮件倾向于攻击或支持政治候选人&#xff0c;因此情绪是一…
阅读更多...
鸿蒙HarmonyOS应用开发之Node-API简介

鸿蒙HarmonyOS应用开发之Node-API简介

场景介绍 OpenHarmony Node-API是基于Node.js 8.x LTS的 Node-API 规范扩展开发的机制&#xff0c;为开发者提供了ArkTS/JS与C/C模块之间的交互能力。它提供了一组稳定的、跨平台的API&#xff0c;可以在不同的操作系统上使用。 本文中如无特别说明&#xff0c;后续均使用Nod…
阅读更多...
顶会热点！迁移学习9个结合创新思路，让审稿人眼前一亮

顶会热点！迁移学习9个结合创新思路，让审稿人眼前一亮

为更灵活、更高效地解决各种复杂和动态变化问题&#xff0c;研究者开始着眼于将迁移学习与其他技术相结合。 这种结合充分发挥了迁移学习的优势&#xff0c;如知识转移、数据效率和加速学习过程等&#xff0c;让模型能够从更高的基准开始学习&#xff0c;更快地适应新任务&…
阅读更多...
多源异构数据种类有哪些？企业该如何利用融合多源数据

多源异构数据种类有哪些？企业该如何利用融合多源数据

随着信息时代的来临&#xff0c;数据的重要性愈发凸显&#xff0c;企业、组织和个人从各种渠道汲取丰富的信息。然而&#xff0c;这些数据往往源自不同的渠道&#xff0c;呈现异构的形式&#xff0c;为数据融合带来了巨大挑战。本文旨在深入研究多源异构数据的种类&#xff0c;…
阅读更多...
人工智能课程小结

人工智能课程小结

人工智能的各种认识论 对人工智能理论的争论 符号主义 (1)人类认知和思维的基本单元是符号 (2)计算机也是—个物理符号系统 (3)认知过程就是在符号表示上的一种运算。 连接主义 (1)人的思维单元是神经元 (2)人脑不同于电脑 行为主义 (1)智能取决于感知和行动&#xf…
阅读更多...
AJAX介绍使用案例

AJAX介绍使用案例

文章目录 一、AJAX概念二、AJAX快速入门1、编写AjaxServlet&#xff0c;并使用response输出字符&#xff08;后台代码&#xff09;2、创建XMLHttpRequest对象&#xff1a;用于和服务器交换数据 & 3、向服务器发送请求 & 4、获取服务器响应数据 三、案例-验证用户是否存…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023