河北省建设工程安全生产网站,科技素材,网站改版公司哪家好,手机影视素材网站大全题目#xff1a;
给定不含重复数字的数组nums,返回其所有可能的全排列#xff0c;可以按任意顺序返回答案 回溯法
一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认不是一个解#xff08;或者至少不是最后一个解#xff09;#xff0c;回溯算法会通…题目
给定不含重复数字的数组nums,返回其所有可能的全排列可以按任意顺序返回答案 回溯法
一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认不是一个解或者至少不是最后一个解回溯算法会通过在上一步进行一些变化抛弃该解即回溯并且再次尝试。
方法一回溯
有 n 个排列成一行的空格从左往右依此填入题目给定的 n 个数每个数只能使用一次。以想到一种穷举的算法即从左往右每一个位置都依此尝试填入一个数看能不能填完这 n 个空格在程序中用「回溯法」来模拟这个过程。
定义递归函数 backtrack(first,output)表示从左往右填到第 first 个位置当前排列为 output。 那么整个递归函数分为两个情况
如果 firstn说明已经填完了 n 个位置注意下标从 0 开始找到了一个可行的解将 output 放入答案数组中递归结束
如果 firstn要考虑这第 first 个位置要填哪个数。根据题目要求不能填已经填过的数因此很容易想到的一个处理手段是定义一个标记数组 vis 来标记已经填过的数那么在填第 first 个数的时候遍历题目给定的 n 个数如果这个数没有被标记过就尝试填入并将其标记继续尝试填下一个位置即调用函数 backtrack(first1,output)。回溯的时候要撤销这一个位置填的数以及标记并继续尝试其他没被标记过的数。
使用标记数组来处理填过的数是一个很直观的思路但是可不可以去掉这个标记数组呢毕竟标记数组也增加了算法的空间复杂度。
答案是可以的可以将题目给定的 n 个数的数组 nums 划分成左右两个部分左边的表示已经填过的数右边表示待填的数在回溯的时候动态维护这个数组即可。
具体来说假设已经填到第 first 个位置那么 nums 数组中 [0,first−1] 是已填过的数的集合[first,n−1] 是待填的数的集合尝试用 [first,n−1] 里的数去填第 first 个数假设待填的数的下标为 i么填完以后将第 i 个数和第 first 个数交换即能使得在填第 first1 个数的时候 nums 数组的 [0,first] 部分为已填过的数[first1,n−1] 为待填的数回溯的时候交换回来即能完成撤销操作。
举个简单的例子假设有 [2,5,8,9,10] 这 5 个数要填入已经填到第 3 个位置已经填了 [8,9] 两个数那么这个数组目前为 [8,9 ∣ 2,5,10] 这样的状态分隔符区分了左右两个部分。假设这个位置要填 10 这个数为了维护数组我们将 2 和 10 交换即能使得数组继续保持分隔符左边的数已经填过右边的待填 [8,9,10 ∣ 2,5] 。
输入nums [1, 2, 3] 目标生成所有可能的排列。 class Solution(object):def permute(self, nums)::type nums: List[int]:rtype: List[List[int]]def backtrack(first0): #定义回溯函数用于递归生成所有排列,first 代表当前正在填充的索引位置默认从 0 开始,该函数的目标是通过交换 nums 中的元素生成所有可能的排列if firstn: #说明 nums 的排列已经完成res.append(nums[:])#nums 的拷贝不能直接 append(nums)否则后续的修改会影响结果for i in range(first,n):#遍历索引 first 到 n-1 之间的所有元素nums[first],nums[i]nums[i],nums[first]#将 nums[i] 交换到 first 位置使其成为当前排列的第 first 个数backtrack(first1)#填充下一个位置的数nums[first],nums[i]nums[i],nums[first]#nums是原地修改的在回溯后需要撤销之前的交换恢复数组原状避免影响其他排列的生成nlen(nums)res[]backtrack()return res
时间复杂度O(n×n!)其中 n 为序列的长度
空间复杂度O(n)其 n 为序列的长度。除答案数组以外递归函数在递归过程中需要为每一层递归函数分配栈空间
源自力扣官方题解
