46. 全排列（中等）-回溯

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

分析

• 回溯法
• 一个是用一个数组记录遍历过的索引
• 另一个是进行数组内的交换
• 参数直接用开始的位置即可
• 结束按照开始位置等于n即可

方案1

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        # 用一个数组记录是否遍历过的索引
        self.n = len(nums)
        used_index = [False] * self.n
        res = []
        def dfs(tmp_list):       
            if len(tmp_list) == self.n:
                res.append(tmp_list[:])
                return

            
            for j, n in enumerate(nums):
                if used_index[j]:
                    continue
                tmp_list.append(n)
                used_index[j] = True

                dfs(tmp_list)

                # 陷阱1， tmp_list = tmp_list[:-1]是建立一个新的tmp list, tmp_list.pop()是原地操作，所以这个更加符合题意
                tmp_list.pop()
                used_index[j] = False

        
        dfs([])

        return res

方案2

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        # 有个进行交换的方案，不需要额外的空间

        n = len(nums)

        res = []
        def backtrack(first = 0):
            if first == n:
                res.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]
        

        backtrack()

        return res