回溯（题单顺序）

把“所有可能”看成一棵决策树，DFS 走下去，走不通就撤销选择（backtrack）换一条路。

• 题意翻译：把数组里的每个数字都用一次，生成所有不同的排列顺序。
• 为什么天然是回溯？
  你可以把它想成“填空题”：
  • 第 1 个位置放谁？
  • 第 2 个位置放谁？
  • … 每一步都有多个候选，选错了就换别的，这正是决策树 + DFS 的场景。
• 状态怎么设计（写回溯最关键的一步）：
  • path：当前已经选出来的前缀排列（长度就是当前深度）
  • used[i]：nums[i] 是否已经被用过（保证“每个元素只用一次”）
• 递归终止条件为什么是 path.length === nums.length？
  因为排列必须用满所有元素，长度达到 n 就是一组完整答案，拷贝 path 记录即可（必须 slice()，否则后面回溯会把它改掉）。
• 回溯的核心动作永远就两步：
  1. 做选择：used[i]=true + path.push(nums[i])
  2. 撤销选择：path.pop() + used[i]=false
• 用一个小例子走一遍：[1,2,3]
  • 先选 1 → 再选 2 → 再选 3 → 得到 [1,2,3]
  • 回退：把 3 弹出，换成 2 的其它选择（这里没有）→ 再回退到 1 的层
  • 让第二个位置换成 3 → 形成 [1,3,2]
  • 再回到第一层把 1 换成 2/3……最终得到 6 种
• 复杂度直觉：分支数是 (n \times (n-1) \times \dots \times 1)，也就是 (O(n!))（输出本身就这么多）。

• 子集的本质：对每个元素只有两种决定——“选它”或“不选它”，所以总数是 (2^n)。
• 为什么还用回溯？：位运算枚举当然能做，但回溯是“组合题通用语言”，后面遇到约束/剪枝时更好扩展。
• start 的意义（避免重复的关键）：
  • 子集不看顺序，所以 [1,2] 和 [2,1] 是同一个。
  • 我们规定：下一次只能从 start 往后选，这样路径永远是按下标递增生成的，自然不会出现顺序颠倒导致的重复。
• 为什么“每到一个节点都要记录一次 path”？
  • 在这棵树里，任何一个节点都代表“当前已经选出来的集合”，它本身就是一个合法子集。
  • 所以进入 dfs(start) 的那一刻，就应该把 path 放进答案。
• 小例子：[1,2,3]
  • 先记录 []
  • 选 1 → 记录 [1] → 再选 2 → [1,2] → 再选 3 → [1,2,3]
  • 回退后改选 3 → [1,3]
  • 回到根层改选 2 → [2]、[2,3]；改选 3 → [3]
  • 一共 8 个，正好 (2^3)。
• 复杂度：输出规模本身是 (2^n)，所以时间/空间至少也是这个量级。

• 把题目看成“固定长度的多叉树”：digits 有几位，就有几层要做选择。
  • 第 pos 层要做的事：从 digits[pos] 对应的字母集合里挑 1 个。
• 为什么回溯很合适？
  • digits 长度不固定（可能 1 位、2 位、4 位……），用回溯就不需要写很多层嵌套循环。
  • 每一层都做同样的动作：“遍历当前可选字母 → 选择一个 → 进入下一层 → 回退”。
• 状态是什么？
  • pos：当前处理到第几位数字
  • path：已经拼好的前缀字符串（用数组存字符，最后 join）
• 终止条件为什么是 pos === digits.length？
  • 说明每一位都已经选了一个字母，路径长度也等于 digits 长度，此时 path.join("") 就是一组完整答案。
• 小例子：digits="23"
  • "2" → a/b/c；"3" → d/e/f
  • 所以答案是 3×3=9 个：ad, ae, ..., cf。
• 复杂度直觉：答案数量本身是各位分支数的乘积（最坏每位 4 个字母，所以最多 (4^n)）。

• 题意翻译：从候选数里选若干个数（允许重复使用同一个候选），凑出 target；输出所有组合（组合不看顺序）。
• 先分清“组合 vs 排列”：
  • 组合不看顺序：[2,2,3] 和 [2,3,2] 应该算同一个答案。
  • 所以我们必须在生成过程中避免“同一组数的不同顺序”。
• start 的意义：保证组合按非递减顺序构造
  • 下一次只能从 start 开始选，等价于“只能选当前数或更大的数”。
  • 这样就不会出现先选 3 再选 2 的情况，自然去重。
• 为什么递归用 dfs(i, remain-x)？
  • 因为题目允许重复使用 candidates[i]，所以选了 x 之后，下一层仍然可以继续选 i（不跳到 i+1）。
• 排序是为了剪枝，不是为了去重：
  • 当候选已排序后，如果 x > remain，后面只会更大，直接 break。
  • 这能大量减少无意义分支。
• 终止条件：
  • remain == 0：刚好凑满，记录 path
  • remain < 0：这条路超了（由于剪枝，代码里不会走到负数）
• 小例子：candidates=[2,3,6,7], target=7
  • 先选 2 → remain=5 → 继续选 2 → remain=3 → 选 3 → remain=0 得到 [2,2,3]
  • 直接选 7 → remain=0 得到 [7]
• 复杂度：本质取决于答案数量与剪枝效果，回溯题通常以“搜索树大小”为主导。

• 为什么这题必须剪枝？：长度是 2n 的括号串一共有 (2^2) 种，先全生成再过滤会爆炸。
• 合法括号串的两条铁律（不变量）：
  1. 最终：左括号和右括号都恰好用 n 个
  2. 过程中任意前缀：右括号数量永远不能超过左括号数量（否则会出现“还没开就先关”的非法状态）
• 把不变量直接写进递归条件，就是最强剪枝：
  • openUsed < n 才能放 '('（否则左括号超量）
  • closeUsed < openUsed 才能放 ')'（保证任意前缀合法）
• 小例子（n=3）帮你理解为什么 closeUsed < openUsed 必须有：
  • 如果一上来就放 ')'，不管后面怎么补，都不可能变成合法串，所以这条分支应该立刻剪掉。
• 终止条件：当 openUsed==n && closeUsed==n，长度正好 2n，且一路都合法，记录答案。
• 复杂度直觉：仍然是指数级（答案数是卡特兰数），但我们只走“可能合法”的分支，实际数量远小于 (2^2)。

• 题意翻译：从某个起点格子出发，走上下左右相邻格子，把经过的字符依次拼成 word；同一格子不能重复使用。
• 为什么这是典型回溯？
  • 你每走一步，都要决定“下一步走四个方向里的哪一个”，这是一棵 4 叉的决策树。
  • 走到一半发现不匹配，就必须退回上一步换方向（这就是 backtrack）。
• 状态定义：
  • (i,j)：当前所在格子
  • k：已经匹配到 word 的第 k 个字符
• 最关键的两个细节（写错就会 WA）：
  1. visited 标记必须是“路径级别”的：同一个格子在同一路径里不能重复用，但换一条路径是可以用的。
     • 所以用“把格子临时改成 #”来表示占用；
     • 递归返回时必须恢复原字符（撤销选择），否则会污染别的起点/别的分支。
  2. 剪枝要越早越好：一进函数就判断 board[i][j] !== word[k]，不匹配立刻 return false，别再扩展四个方向。
• 为什么要从每个格子都试起点？：word 的第一个字符可能出现在任意位置，起点不固定。

• 题意翻译：把字符串切成若干段，每段都是回文，输出所有切法。
• 回溯树怎么长（核心建模）：
  • 站在位置 start，你要决定“下一刀切到哪里 end”。
  • 只要 s[start..end] 是回文，这一刀就合法，递归去处理 end+1。
  • 当 start == n，说明刚好切到末尾，path 就是一种完整切法。
• 性能瓶颈在哪里？：回溯会反复问同一句话：“这段子串是不是回文？”
  • 如果每次都现用双指针检查，会在不同分支里重复检查同一段子串，成本很高。
• 关键优化：先用 DP 把所有回文子串预处理出来：
  • pal[i][j] 表示 s[i..j] 是否回文，回溯时直接 (O(1)) 查表。
• DP 为什么这样填表（推理顺序）：
  • s[i] === s[j] 且内部 s[i+1..j-1] 是回文 ⇒ pal[i][j]=true
  • 但这依赖 pal[i+1][j-1]，所以 i 要从右往左枚举（保证内部先算好），j 从 i 往右扩展。
  • j-i <= 2（长度 1/2/3）时内部为空或单字符，可直接作为 base case。
• 小例子："aab"
  • a | a | b（每段都是回文）
  • aa | b（"aa" 也是回文）
• 复杂度：DP 预处理 (O(n^2))，回溯输出规模取决于答案数量（最坏指数级），但查回文变成了常数。

• 题意翻译：在 n×n 棋盘上放 n 个皇后，要求任意两个皇后都互不攻击（同列/同对角线都不行；按“逐行放”会天然避免同行冲突）。
• 为什么按“行”回溯是最优建模？
  • 规则里隐含了一个强约束：每一行最多放 1 个皇后（否则同行必冲突）。
  • 所以我们把第 r 层定义为“给第 r 行选一个列 c”，这会大幅减少无效状态。
• 三个集合剪枝是怎么推理出来的？
  • 列冲突：同列不能放 → 用 cols 存已占用列 c
  • 主对角线冲突：同一条主对角线满足 r-c 相等 → 用 diag1 存 r-c
  • 副对角线冲突：同一条副对角线满足 r+c 相等 → 用 diag2 存 r+c
• 为什么这三类就够了？：皇后的攻击路径只有“竖直”和“两条斜线”，不存在其它方向，所以只要这三类都不冲突，就一定安全。
• 回溯的撤销动作要配套：
  • 放置时：往三套集合里 add + 在棋盘写 Q
  • 回退时：从三套集合里 delete + 恢复 .
• 复杂度直觉：最坏接近 (O(n!)) 的搜索（每行选一列），剪枝会大幅减少实际分支。