图解算法通识讲义树与图
回溯算法与递归决策树剪枝
核心心智模型：穷举试探，撞墙回头；做选择、递归深入、撤销选择，在决策空间树中搜寻全部可行路径。
核心交互式算法图解演练沙盒
回溯剪枝模型
全排列状态决策树与回溯撤销现场演练
步骤 1 / 4
当前递归路径 Path:[1]
↓ 深入下一分支
可用元素候选池与访问标记数组 used[]
1
used = true (已占用)
2
used = false (可选)
3
used = false (可选)
做出选择：在候选池 [1, 2, 3] 中选择 1 加入 path，标记 used[0]=true，继续向下递归深入。
关键操作与时空复杂度速查对照表
| 操作 / 算法阶段 | 平均时间 | 最坏时间 | 空间复杂度 | 核心底层机制 |
|---|---|---|---|---|
| 全排列搜索 | O(N!) | O(N!) | O(N) | N 个元素的全排列共有 N! 种叶子节点。 |
| 子集搜索 | O(2^N) | O(2^N) | O(N) | 每个元素有选与不选两种状态，解空间 2^N。 |
template.java
List<List<Integer>> res = new ArrayList<>();
List<Integer> track = new ArrayList<>();
boolean[] used = new boolean[nums.length];
void backtrack(int[] nums) {
if (track.size() == nums.length) {
res.add(new ArrayList<>(track));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true;
track.add(nums[i]);
backtrack(nums);
track.remove(track.size() - 1);
used[i] = false;
}
}解题核心心法提炼
- 子集问题是收集决策树的每个节点；排列与组合问题是在叶子节点收集结果。
- 组合问题需传入 startIndex 防止逆向选取产生重复；排列问题需传入 used 布尔数组。
- 收集结果加入 ans 时，务必深拷贝列表（如 new ArrayList<>(track)），否则后续撤销会导致结果被洗空。
常见踩坑警示与避坑指南
- 忘记在递归调用后执行撤销操作（track.remove / used=false）。
- 收集答案时直接传入引用 ans.add(track) 导致最终全为空列表。
对应 Hot 100 实战题目突围
原理已掌握！立即进入沉浸式工作台开始实战演练，强化代码肌肉记忆