leetcode46. 全排列

题目

全排列
思路

使用深度优先&递归方法来做
不断地抽取其中一个数字，剩余数字构成子问题：1+[2,3]、2+[1,2]、3+[1,2]
停止条件是len(list)==1时候开始从最底层开始返回

注意点

不断生成的是list套list，不能直接将一个数字加上list，比如1+[2,3]≠[1,2,3]，正确的写法是[1]+[2,3]=[1,2,3]，更不要幻想1+[[2,3],[3,2]]=[[1,2,3],[1,3,2]]，正确的做法是利用循环遍历出来进行加法

提取的时候也要注意，这个是有放回式的抽取，剩余应该这样提取rest = nums[:i] + nums[i + 1:]

注意输入本身就是空值

#python3
class Solution:
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums) == 0:
            return []
        if len(nums) == 1:
            return [nums]
        res=[]
        for i in range(len(nums)):
            # res.append(nums[i]+self.permute([nums[i:]]))
            prefix = nums[i]
            rest = nums[:i] + nums[i + 1:]
            for j in self.permute(rest):
                res.append([prefix] + j)
        return res

sol = Solution()
print(sol.permute([1,2,3]))

另一个思路

提炼深度遍历dfs(nums, path, res)
nums是呆遍历的子问题，path是代拼接部分，res是子问题的结果
停止条件是dfs时候nums已空

注意

path初始化是空list

class Solution:
    # DFS
    def permute(self, nums):
        res = []
        self.dfs(nums, [], res)
        return res

    def dfs(self, nums, path, res):
        if not nums:
            res.append(path)
            # return # backtracking
        for i in range(len(nums)):
            self.dfs(nums[:i]+nums[i+1:], path+[nums[i]], res)