[leetcode]46. 全排列

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

示例:

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

[3,1,2], [3,2,1] ]

解法

还是回溯算法。

思路还是很简单的，本来以为可以很轻松写完，却碰到了两个大坑：python的list复制和顺序问题。

按照惯例，先贴出自己写的代码：

class Solution:
    def __init__(self):
        super().__init__()
        self.length = None
        self.ans = []

    def permute(self, nums: List[int]) -> List[List[int]]:
        self.length = len(nums)
        now = []
        self.walk(now, nums)
        return self.ans

    def walk(self, now, left):
        if len(now) == self.length:
            self.ans.append(now.copy())
            return

        for i in range(len(left)):
            num = left.pop(i)	#从left中取出第i个数据
            now.append(num)		#加入到now
            self.walk(now, left)#walk
            now.pop()			#从now取出
            left.insert(i,num)	#放回left
           

有了回溯的思想后，思路其实非常简单：按顺序从list中一个一个抽数字，所有的数字被抽完之后，就得到了一个可行解。详细来说：

1. 假设一开始数据为[1,2,3]，
2. 按顺序取第一个，得到[1] #####最终回溯到这里，第一个取的将会是2或者3
3. 剩下的是[2,3]，
4. 再按顺序取剩下的，得到[1,2] 最终回溯到这里，剩下的2，3取3
5. 剩下[3]
6. 得到一个解
7. 回溯

在这我把用了两个list，分别是now和left，分别代表现在抽了的数据和剩下的数据。一开始now为空，而left就是原始数据。

代码优化

from typing import List
class Solution:
    def __init__(self):
        super().__init__()
        self.length = None
        self.ans = []

    def permute(self, nums: List[int]) -> List[List[int]]:
        self.length = len(nums)
        now = []
        self.walk(now, nums)
        return self.ans

    def walk(self, now, left):
        if len(now) == self.length:
            self.ans.append(now)		# 可以不用copy
            return

        for i in range(len(left) ):
            # num = left.pop(i)
            # now.append(num)
            # self.walk(now, left)
            # now.pop()
            # left.insert(i,num)
            self.walk(now+[left[i]],left[:i]+left[i+1:])	# 简化

           

list的复制

>>> a = []
>>> b = [1,2,3]
>>> a.append(b)
>>> b.pop()
3
>>> b
[1, 2]
>>> a
[[1, 2]]
           

假如我这里直接操作b，那么a也会发生变化。

顺序问题

这里的顺序是指从left取数据一定要按顺序，从哪里取出来的必须插回哪里。