算法困惑问答 · LC 46 全排列
回溯算法为什么要撤销选择？不撤销会怎样？
直接答案
因为整棵决策树的所有分支共用同一份 path 和 used 状态。递归返回意味着「这个分支的所有可能都枚举完了」，必须把进入分支时做的选择擦掉（path.pop、used 复位），下一个兄弟分支才能在干净的现场上做自己的选择。不撤销的后果立竿见影：path 越堆越长、used 一直占着，第一条分支之后的所有分支都在被污染的状态上枚举，结果大面积缺失或混入错误方案。
决策树视角：进门做选择，出门必须还原
把全排列的枚举过程画成一棵树：第一层选第一个数，第二层选第二个数……DFS 走到叶子收获一个排列，然后原路返回。返回到某个节点时，程序即将走它的下一个子分支——比如刚枚举完「以 1 开头」的所有排列，要开始「以 2 开头」。此时 path 里必须只剩公共前缀、1 的 used 标记必须已释放，否则「以 2 开头」的世界里会残留着 1 的痕迹。
所以「做选择」和「撤销选择」永远成对出现，一进一出把递归调用夹在中间。这也是回溯和普通 DFS 的分野：回溯复用同一份状态、靠撤销回收现场；如果每层递归都拷贝一份新状态，就不需要撤销，但每层 O(n) 的拷贝把效率吃掉了。
另一个连环坑：收录答案要存拷贝
走到叶子时写 res.append(path) 是错的——append 进去的是 path 这个对象的引用，而 path 马上就要被 pop 反复修改。程序跑完你会发现 res 里所有「排列」都变成了同一个（通常是空列表）。正确写法是存快照：res.append(path[:])（或 list(path)）。
这两个坑本质是同一件事的两面：回溯为了效率共享一份可变状态，所以「离开时要还原、留档时要拷贝」。记住这句话，绝大多数回溯 bug 都能自己排掉。
代码关键行（Python）
def permute(nums):
res, path = [], []
used = [False] * len(nums)
def backtrack():
if len(path) == len(nums):
res.append(path[:]) # 存拷贝，不存引用
return
for i in range(len(nums)):
if used[i]: continue
path.append(nums[i]); used[i] = True # 做选择
backtrack()
path.pop(); used[i] = False # 撤销选择
backtrack()
return res「做选择」和「撤销选择」把 `backtrack()` 夹在中间、逐项对应（append↔pop、置 True↔置 False）。少写任何一半，决策树从那个节点往后全部走样。
常见追问
回溯和 DFS 是一回事吗？
回溯就是带撤销的 DFS。DFS 是遍历方式；回溯强调在遍历决策树时通过「做选择 / 撤销选择」复用同一份状态。数连通块那种一去不回头的 DFS 不需要撤销，枚举方案的 DFS 才叫回溯。
能不能不用 used 数组？
全排列可以用「交换法」：把第 i 位和后面每个数交换后递归、返回时换回来——交换回来这步依然是撤销，只是换了形式。撤销这件事逃不掉，变的只是载体。
把这道题彻底吃透
LC 46「全排列」有逐步交互动画和完整图文题解，配着本页的结论看，一遍就通。