题目定位
和子集不同，这里顺序重要，因此每一层都要从未使用元素中选一个，并把它标记为已用。
关键观察
每一层递归都在固定排列中的一个位置。
目标复杂度
O(n * n!) / O(n)
这题的解法思路怎么拆
1
和子集不同，这里顺序重要，因此每一层都要从未使用元素中选一个，并把它标记为已用。
2
每一层递归都在固定排列中的一个位置。
3
先把决策树结构建出来。
4
确定当前层候选集怎么生成。
参考实现
Python# Generic pattern template
def backtrack(path):
if complete(path):
answer.append(path[:])
return
for choice in choices(path):
if not valid(choice, path):
continue
path.append(choice)
backtrack(path)
path.pop()
常见坑点
warning
递归返回后忘记恢复 used 标记。
warning
重复把同一个 path 引用塞进答案。
高频追问
如果数组有重复元素，怎样避免重复排列？
能不能改写成交换法？
继续刷相关题
先把 回溯 这个模式刷成体系，再去做更难变体。