每日一道算法题--leetcode 46--全排列--python

【题目描述】

最终要返回的是一个list的嵌套，也就是说终止条件一定是将list放入list中。利用深度优先搜索，终止条件是指针到结尾处。每一层递归其实是不断固定第一位，固定前两位，固定前三位，形成一棵树结构，到叶子节点时，不断回溯还原原数组，以供其兄弟节点使用该数组。

以下是形成的树结构。为什么说这是深度优先呢？因为都是沿着一条路径走到不能再走的地步才开始回溯的。

【源代码】

def permute(self, nums):
        def backtrack(first=0):
            if first == n:  
                output.append(nums[:])
            for i in range(first, n):
                nums[first], nums[i] = nums[i], nums[first]
                backtrack(first + 1)
                nums[first], nums[i] = nums[i], nums[first]
        
        n = len(nums)
        output = []
        backtrack()
        return output