[backtracking] full arrangement leetcode46

Give an array without duplicate numbers nums , Back to its All possible permutations . You can In any order Return to the answer .
Example 1：

Input ：nums = [1,2,3] Output ：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Example 2：

Input ：nums = [0,1] Output ：[[0,1],[1,0]]
Example 3：

Input ：nums = [1] Output ：[[1]]
link ：https://leetcode.cn/problems/permutations

Very classic backtracking algorithm problem foundation , Consider the state of the recursive tree 、 What are variables and returns , In this question , The variables of the recursion tree are the variables of each recursion nums, The root node is itself , Each recursion reduces the number by one , The leaf node is nums When it's empty , Go back .

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

        '''NOTE 1. Thinking about recursive trees （ What are the root and intermediate nodes ） 2. Think about each state of the recursive tree （for The loop condition ） 3. Think about the variables of the recursive tree （ Formal parameters of the backtrace function ） 4. Think about what the leaf nodes of a recursive tree are （ Where to end return And save what ） '''
        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