题解 | 没有重复项数字的全排列

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param num int整型一维数组 
# @return int整型二维数组
#
from copy import deepcopy
# class Solution:
#     def permute(self , num: List[int]) -> List[List[int]]:
#         def backtrack(chose, choices: list[int], res: list[int]):
#             """回溯算法框架"""
#             # 判断是否为解
#             if len(chose)==len(num):
#                 # 记录解
#                 res.append(chose)
#                 # 不再继续搜索
#                 return
#             # 遍历所有选择
#             for ind,choice in enumerate(choices):
#                 chose.append(choice)
#                 choices.pop(ind)
#                 backtrack(chose, choices, res)
#                 # 回退：撤销选择，恢复到之前的状态
#                 chose.pop()
#                 choices.insert(ind,choice)
#         results = []
#         backtrack([],num,results)
#         return results

class Solution:
    def permute(self , num: List[int]) -> List[List[int]]:
        results = []
        
        def backtrack(chose, choices):
            # 判断是否为解
            if len(chose) == len(num):
                # 记录解：此处必须使用深拷贝
                results.append(chose[:])  # 或者 results.append(list(chose))
                return
            
            # 遍历所有选择
            for ind, choice in enumerate(choices):
                # 做选择
                chose.append(choice)
                # 注意这里递归调用时，也需要传递新的 choices 列表，避免引用问题
                new_choices = choices[:ind] + choices[ind+1:]
                backtrack(chose, new_choices)
                chose.pop()
        
        backtrack([], num)
        return results