1、题目描述：

2、题解：

回溯算法框架：

result = []
def backtrack(选择列表，路径):if 满足结束条件:result.add(路径)returnfor 选择 in 选择列表:做选择backtrack(选择列表，路径)撤销选择# 做选择
将该选择从选择列表移除
路径.add(选择)# 撤销选择
路径.remove(选择)
将该选择再加入选择列表解决一个回溯问题，实际上就是一个决策树的遍历过程：
1、路径：也就是已经做出的选择。
2、选择列表：也就是你当前可以做的选择。
3、结束条件：也就是到达决策树底层，无法再做选择的条件。

可以把「路径」和「选择」列表作为决策树上每个节点的属性
框架的解释：

class Solution:def permute(self, nums: List[int]) -> List[List[int]]:res = []#路径记录在temp中def backtrack(nums, temp):if not nums:res.append(temp)returnfor i in range(len(nums)):backtrack(nums[:i] + nums[i+1:], temp + [nums[i]])backtrack(nums, [])return res

3、复杂度分析：

时间复杂度：O(N*N!)
空间复杂度：O(N)