页面加载中…
一套『做选择→递归→撤销』模板，解锁子集、组合、排列、切割、棋盘全系列
回溯本质是「在决策树上深度优先遍历，走不通就原路退回」。从子集问题建立三要素（路径/选择列表/终止条件），再逐步引入 start 指针、used[] 去重、剪枝等武器。全程只靠一个模板，覆盖 Hot100 中 6 道高频题，是面试必备的思维框架。
适合：想掌握『选择-递归-撤销』模板的人
建立回溯三要素：路径（已选列表）、选择列表（剩余候选）、结束条件。用 start 指针控制「向后选」避免重复组合；每进入一层前先把当前路径加入结果，退出时弹出最后一个元素完成撤销。
回溯入口题：建立『做选择→递归→撤销选择』三步模板，每个节点都收进结果集，start 指针保证子集不重不漏。
上一题无重复元素，直接枚举即可。这题数组有重复，在同一层循环中跳过与前一个相同的元素（需先排序），沿用同一 start 模板加一行剪枝。
子集每层都收结果；组合只收路径长度恰好为 k 的叶子。改造终止条件，再加『剩余数量不足 k-len』的早剪，其余框架与子集完全相同。
组合题中每个元素只选一次；这题元素可重复选，递归时 start 不后移而留在当前位，同时以 target 递减做剪枝替代长度判断。
组合用 start 指针限制方向，排列不限方向但不能重用同一位置，改用 used[] 布尔数组标记。去重逻辑（排序+同层跳过）在组合 II 和全排列 II 中复用，要注意『同层去重』和『同支去重』的区别。
元素有重复且每个只用一次。在 combination-sum 上改 start+1；同层 nums[i]==nums[i-1] 跳过，去重与子集 II 同款。
组合靠 start 避免倒序重选；排列需要所有位置的全排，于是抛弃 start，改用 used[] 标记哪些索引已在当前路径中，路径满 n 位时收结果。
全排列 I 靠 used[] 去位；这题排序后加同层剪枝：!used[i-1] 且值相同时跳过，与子集 II 同层去重逻辑完全一致。
前几题候选集固定；这题每层候选集由数字映射字母决定，递归参数从 start 换成数字下标 index，层深等于串长度。
回溯可以在字符串上切割（分割型）、在棋盘格上逐行放置（约束型）、在二维网格上四向 DFS（图搜索型）。三类问题的模板骨架不变，差异在于合法性判断的复杂度：切割判回文、棋盘判列/对角线、网格判边界与访问标记。