【回溯】全排列 leetcode46

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：

输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：

输入：nums = [0,1] 输出：[[0,1],[1,0]]
示例 3：

输入：nums = [1] 输出：[[1]]
链接：https://leetcode.cn/problems/permutations

很经典的回溯算法题基础，需要考虑递归树的状态、变量和返回是什么，在此题中，递归树的变量是每一次递归时的nums，根节点是本身，每一次递归会减少一个数，叶子节点就是nums为空的时候，进行返回。

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

        '''NOTE 1.思考递归树（根节点和中间节点是什么） 2.思考递归树的每一个状态（for循环条件） 3.思考递归树的变量有哪些（回溯函数的形参） 4.思考递归树的叶子节点是什么（到哪结束return并保存什么） '''
        def helper(nums:list,his:list):
            if len(nums)==0:
                self.ret.append(his)
                return
            for idx in range(len(nums)):
                helper(nums[:idx]+nums[idx+1:],his+[nums[idx]])

        helper(nums,[])

        return self.ret