回溯（Backtracking）

用递归 + 枚举试遍所有可能，走不通就回退（恢复状态），常配合剪枝减少无效分支。排列、组合、子集、棋盘类题常用。

思路

1. 选择：当前步有哪些选项（例如选哪个数、放哪一列）。
2. 递归：做一种选择后进入下一层。
3. 撤销：退回当前层时恢复状态，再试下一个选项。

子集（无重）

求数组的所有子集（2^n 个）。每次递归「选或不选」当前元素，到末尾时把当前路径加入结果。

全排列（无重）

求数组的全排列。用 used 记哪些已选，枚举每个未选数作为当前位，递归后撤销。

组合（选 k 个）

从 n 个数里选 k 个，无重、不计顺序。按「从哪一位开始选」递归，避免重复（只往后选）。

小结

• 状态：当前路径 path、已用标记 used 等，递归前改、递归后一定恢复。
• 剪枝：不满足条件时 continue 或提前 return，少走无效分支。
• 子集/排列/组合是回溯的经典形式，很多题是在此基础上加条件（去重、和为 target 等）。