leetcode-全排列

题目描述

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

输入输出

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

算法思想

这个问题可以看作有 n 个排列成一行的空格，我们需要从左往右依此填入题目给定的 n 个数，每个数只能使用一次。那么很直接的可以想到一种穷举的算法，即从左往右每一个位置都依此尝试填入一个数，看能不能填完这 n 个空格，在程序中我们可以用「回溯法」来模拟这个过程。

我们定义递归函数 backtrack(first, output) 表示从左往右填到第 first 个位置，当前排列为 output。 那么整个递归函数分为两个情况：

1. 如果 first==n，说明我们已经填完了 n 个位置（注意下标从 0 开始），找到了一个可行的解，我们将 output 放入答案数组中，递归结束。
2. 如果 first

示意图

代码实现

class Solution:
    def permute(self,nums:List[int]) -> List[List[int]]:

        size = len(nums)
        ans = []
        def backtrack(first=0):
            # 所有的数字都填完了，返回一个排列结果
            if first == size:
                ans.append(nums[:])
            
            for i in range(first,size):
                nums[first],nums[i] = nums[i],nums[first]
            
                # 继续递归填入下一个数
                backtrack(first+1)

                #撤销操作
                nums[first],nums[i] = nums[i],nums[first]

        backtrack()

        return ans