leetcode 46 全排列

通过回溯算法，在纸上画出求解问题的树形图，想清递归结构考虑如何剪枝。

做题的时候，建议 先画树形图 ，画图能帮助我们想清楚递归结构，想清楚如何剪枝。拿题目中的示例，想一想人是怎么做的，一般这样下来，这棵递归树都不难画出。

在画图的过程中思考清楚：

分支如何产生；
题目需要的解在哪里？是在叶子结点、还是在非叶子结点、还是在从跟结点到叶子结点的路径？
哪些搜索会产生不需要的解的？例如：产生重复是什么原因，如果在浅层就知道这个分支不能产生需要的结果，应该提前剪枝，剪枝的条件是什么，代码怎么写？

！！！#需要注意得到数组的浅复制，尤其是python

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:

        def dfs(index,path,result):
            if index==len(nums):
                result.append(path[:])#注意这个地方，得到path数组的浅复制

                return

            for i in range(len(nums)):
                if nums[i] in path:continue
                path.append(nums[i])
                dfs(index+1,path,result)
                path.pop()#path[:]=path[:-1]

        path=[]
        result=[]
        dfs(0,path,result)
        return result

作者：liweiwei1419
链接：https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

递归，每次通过path+[]来进行复制，构造一个新的空间，不用回溯。

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:

       def dfs(i,path,result):
           if i==len(nums):
               result.append(path)

               return
           for j in range(len(nums)):
                if nums[j] in path:continue
                dfs(i+1,path+[nums[j]],result)

       result=[] 
       dfs(0,[],result)
       return result