当前位置: 首页> 财经> 金融 > 鞍山微信小程序定制开发_上海市网站建设定制_bt磁力狗_优化网站建设

鞍山微信小程序定制开发_上海市网站建设定制_bt磁力狗_优化网站建设

时间:2025/7/11 3:32:37来源:https://blog.csdn.net/qq_65509025/article/details/145981326 浏览次数:0次
鞍山微信小程序定制开发_上海市网站建设定制_bt磁力狗_优化网站建设

1、题目描述

给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1:

输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

2、先验知识

2.1 回溯算法

回溯法也可以叫做回溯搜索法,它是⼀种搜索的方式。回溯是递归的副产品,只要有递归就会有回溯。虽然回溯法很难,很不好理解,但是回溯法并不是什么⾼效的算法。因为回溯的本质是穷举,穷举所有可能,然后选出我们想要的答案,如果想让回溯法⾼效⼀些,可以加⼀些剪枝的操作,但也改不了回溯法就是穷举的本质。

但是面对一些问题,能用穷举法求解已经是最优算法,比如以下问题:

  • 组合问题:N个数里面按一定规则找出k个数的集合

  • 切割问题:一个字符串按一定规则有几种切割方式

  • 子集问题:一个N个数的集合里有多少符合条件的子集

  • 排列问题:N个数按⼀定规则全排列,有几种排列方式

  • 棋盘问题:N皇后,解数独等等

2.2 回溯算法模板(python)

def backtracking(参数):#参数可根据实际情况进行修整if(终止条件):收集结果returnfor (集合中的元素):处理节点递归回溯return

3 全排列

3.1 思路

全排列的树结构可表示如下:

根据模板进行分析

(1)终止条件

当path的长度和nums的长度相同时,表示path已经得到了一个全排列组合,此时终止;

(2)收集结果

将终止时,path加入到结果res中,需要注意的是,由于回溯的撤销操作,path会不断发生改变,在添加结果时,应当使用path.copy(),防止后续修改影响已保存的结果;

(3)集合中元素

从给定的nums中进行选择

(4)处理节点

从nums中任选一个元素将其加入到path中

(5)递归

根据path的长度和变化的集合进行递归,变化的集合表示为s-{path}中已经存在的元素

(6)回溯

在 path[i] = x 赋值后,递归处理下一层。当递归返回时,当前层的循环继续执行,下一个 x 会直接覆盖 path[i] 的值,自然实现了状态的“回退”。因此,在本代码中无需显式撤销操作。

(7)参数

根据上述分析,可见递归的参数可表示为path的长度和变化的集合

3.2 完整代码

根据上述分析,可以得到完整代码:

class Solution:def permute(self, nums: List[int]) -> List[List[int]]:n = len(nums)res = []path = [0] * ndef backtracking(i,s):if i == n:res.append(path.copy())returnfor x in s:path[i] = xbacktracking(i+1, s-{x})backtracking(0,set(nums))return res
关键字:鞍山微信小程序定制开发_上海市网站建设定制_bt磁力狗_优化网站建设

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: