46. 全排列（Python）

更多精彩内容，请关注【力扣中等题】。

题目

难度：★★★☆☆
类型：数学
方法：回溯法

题目

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

示例

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

解答

全排列其实可以使用python内置的permutations函数，例如求['a', 'b', 'c']的全排列，可以使用：itertools.permutations(['a', 'b', 'c'],3)快速得到。这里参考了大佬博客。

方案1：回溯法

我们举个例子，以字符串列表['a', 'b', 'c']为例，我们逐个位确定全排列的所有可能。回溯法的原理在于在前n-1位元素确定的情况下，求取n位以后的全排列。本例中，首先固定第0位，就是分别将第0位与它本身及后面各位元素交换，得到3种不同的可能，在固定这一位后，在考虑第1位的可能性，将第1位与它本身及其后元素交换，有两种可能性，当前两位元素确定后，最后一位只有一种可能性。因此一共有6种可能。

1. 将列表的第0位与第0位交换（相当于不变），此时列表变为['a', 'b', 'c']；
   1.1 将列表的第1位与第1位交换（相当于不变），得到列表['a', 'b', 'c']；
   1.2 将列表的第1位与第2位交换，得到列表['a', 'c', 'b']；

2. 将列表的第0位与第1位交换，得到列表['b', 'a', 'c']；
   2.1 将列表的第1位与第1位交换（相当于不变），得到列表['b', 'a', 'c']；
   2.2 将列表的第1位与第2位交换，得到列表['b', 'c', 'a']；

3. 将列表的第0位与第2位交换，得到列表['c', 'b', 'a']；
   3.1 将列表的第1位与第1位交换（相当于不变），得到列表['c', 'b', 'a']；
   3.2 将列表的第1位与第2位交换，得到列表['c', 'a', 'b']

这里需要注意的是，每次交换元素并回溯寻找后，都要将元素交换回来，保持没有交换前的状态。

class Solution:
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """

        def backtrack(position, end):
            """
            Find possible results using backtrack.
            :param position:
            :param end:
            :return:
            """

            if position == end:
                res.append(nums[:])
                return

            for index in range(position, end):
                nums[index], nums[position] = nums[position], nums[index]
                backtrack(position + 1, end)
                nums[index], nums[position] = nums[position], nums[index]

        res = []
        backtrack(0, len(nums))
        return res

方案2：深度优先搜索

与回溯法类似，增加临时列表用来存储是否查看过变量。

class Solution:
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """

        visit = [True for _ in range(len(nums))]
        tmp = nums[:]

        def dfs(position):
            if position == len(nums):
                res.append(tmp[:])
                return

            for index in range(0, len(nums)):
                if visit[index]:
                    tmp[position] = nums[index]
                    visit[index] = False
                    dfs(position + 1)
                    visit[index] = True

        res = []
        dfs(0)
        return res

如有疑问或建议，欢迎评论区留言~