46. 全排列

题目

• 题号：46
• 难度：中等
• https://leetcode-cn.com/problems/permutations/

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例1

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

实现

思路1 深搜+回溯

此题只需要将我们枚举全排列的思路进行编程，其实就是深搜+回溯的方法。如下图：

首先解决深度优先遍历问题需要定义状态，上图中每个节点的list互不相同，就是一个状态变量，因为它们可以表示当前处于搜索过程中的什么阶段。这里可以定义一个path变量来存储这个list。并且在DFS中，这个path是一个栈（BFS是队列），因为往下遍历一层的时候，需要对path尾部增加一个数字，而回溯的时候需要在path尾部删除一个数字。
然后我们需要定义目标状态，如果通过叶子节点作为目标状态进行匹配则有非常多的目标状态。这里全排列问题其实只需要考虑数字是否全部用完，如果全部用完了就是一个目标状态。而看数字是否用完其实可以通过查看遍历的层次，当depth==len(nums)，就说明数字已经都用上了，可以终止递归了。因此这里需要定义一个depth表示当前遍历的深度。
此外为了DFS遍历时不会遍历已经访问过的数字，每次要访问一个新的数字前需要先查看该数字是否已被使用过，因此需要再对path遍历一遍。这里为了节省时间，可以用一个以空间换时间的方法，即定义一个visit变量存放一个list，来记录某个数字是否已被使用过。若被使用，只需要将数字对应的下标位置的值设为true，就可以以的时间很快查看数字是否使用过。

最后要注意的是回溯后，也要将状态变量都设置为跟之前状态一样（状态重置）。

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def backtrack(nums, size, depth, path, visit, res):
            if depth == size:
                res.append(path[:]) # 这里要特别注意做一次拷贝
                # 否则对象变量在传参过程中复制的是变量的地址
                # 而path最后会回溯为空，res里保存的也就都是空的list
                return

            for i in range(size):
                if not visit[i]:
                    visit[i] = True
                    path.append(nums[i])
                    # 继续往下一层遍历
                    backtrack(nums, size, depth + 1, path, visit, res)
                    # 回溯
                    visit[i] = False
                    path.pop()

        size = len(nums)
        visit = [False for _ in range(size)]
        res = []
        backtrack(nums, size, 0, [], visit, res)
        return res

思路2 左右交换

思路来源于官网解答，即基于思路1改进，不用定义visit这个标记数组来记录数字是否使用过。
方法是将nums划分成左右两个部分，左边的表示已经填过的数，右边表示待填的数。在递归搜索的时候只要动态维护这个数组即可。举个例子，假设我们有 [2, 5, 8, 9, 10] 这 5 个数要填入，现在已经填了 [8,9] 两个数，需要再决定第三个数字加入。那么这个数组目前为 [8, 9 | 2, 5, 10] 的状态，分隔符区分了左右两个部分。假设这个位置我们要填 10 这个数，为了维护数组，我们将 2 和 10 交换，即能使得数组继续保持分隔符左边的数已经填过，右边的待填 [8, 9, 10 | 2, 5]。回溯后则再执行一次交换操作，就恢复为回溯前的状态了。

class Solution:
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        def backtrack(depth = 0):
            # 所有数都填完了
            if depth == n:  
                res.append(nums[:])
            for i in range(depth, n):
                # 动态维护数组
                nums[depth], nums[i] = nums[i], nums[depth]
                # 继续递归填下一个数
                backtrack(depth + 1)
                # 撤销操作
                nums[depth], nums[i] = nums[i], nums[depth]

        n = len(nums)
        res = []
        backtrack()
        return res

时间复杂度：**上述两个思路均为。调用backtrack的次数是的，另外将当前答案复制到答案数组中需要时间。

Reference
https://leetcode-cn.com/problems/permutations/solution/quan-pai-lie-by-leetcode-solution-2/