2019-05-21LeetCode 46.全排列

借鉴

     def permute(self, nums: List[int]) -> List[List[int]]:
         return [[n]+p for i,n in enumerate(nums) for p in self.permute(nums[:i]+nums[i+1:])] or [[]]

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        if not nums:return [[]]  # 这个是因为如果不特殊处理， self.permute(nums[:i]+nums[i+1:])为空的话res.append([n]+p)不处理
        res=[]
        for i,n in enumerate(nums):
            for p in self.permute(nums[:i]+nums[i+1:]):
                res.append([n]+p)
        return res or[[]]

上面的思路是递归的思路，
下面是采用回溯的思路，将结果作为参数传递下去

class Solution2:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res=[]
        self.dfs(nums,[],res)
        return res

    def dfs(self,nums:List[int],path:List[int],res:List[List[int]]):
        if not nums:
            res.append(path)
        for i,n in enumerate(nums):
            self.dfs(nums[:i]+nums[i+1:],path+[n],res)

由于别的语言没有切片这么方便的操作，所以通过第一个元素与后面每一个元素进行交换，使得只要传递第一个元素后面的元素，即是替代了切片操作出去fixed的第一个元素。交换之后，除了第一个元素剩下的元素就是回溯法当前层的可选集了，但是元素不能再是字典序了。

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res=[]
        self.dfs(nums,[],res)
        return res


    def dfs(self,nums,path:List[int],res):
        if not nums:res.append(path+[]);return # 千万注意这里append是一个引用
        for j,_ in enumerate(nums):
            # print(nums[0],nums[j])  # 整个流程思路没错的话，应该就是细节和语法问题，最后发现是由于j是一个复制，不是引用，不会改变原数组
            nums[0], nums[j]=nums[j],nums[0]
            path.append(nums[0])
            self.dfs(nums[1:],path,res)
            path.pop()
            nums[0], nums[j]=nums[j],nums[0]

1.res.append(l）是一个引用
2.for j in nums 是一个复制