分割回文串如何用回溯法求解？（LeetCode 131）

简化版

把字符串切成若干段，要求每一段都是回文串，返回所有切法。这是「切割型」回溯：决策不是「选哪个元素」，而是「在哪里切一刀」。用 start 表示当前从哪开始切，枚举切割终点 end，只有 [start, end] 是回文时才切下这一段并递归处理剩余部分；start 走到字符串末尾就收集一种切法。「只有回文才切」就是这题的核心剪枝。

详细版

List<List<String>> partition(String s) {
    List<List<String>> res = new ArrayList<>();
    backtrack(s, 0, new ArrayList<>(), res);
    return res;
}
void backtrack(String s, int start, List<String> path, List<List<String>> res) {
    if (start == s.length()) {                 // 切到末尾，得到一种完整切法
        res.add(new ArrayList<>(path));
        return;
    }
    for (int end = start; end < s.length(); end++) {
        if (isPalindrome(s, start, end)) {     // 剪枝：只有回文子串才切这一刀
            path.add(s.substring(start, end + 1));  // 做选择：切下 [start, end]
            backtrack(s, end + 1, path, res);       // 递归处理剩余 [end+1, ...]
            path.remove(path.size() - 1);           // 撤销
        }
    }
}
boolean isPalindrome(String s, int l, int r) {
    while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
    return true;
}

切割型的选择 = 切割终点 end：[start, end] 是当前切下的这一段。
剪枝：非回文的段直接跳过，不递归。
start 到末尾（start == s.length()）作为结束条件——整个串刚好被切完。
递归传 end + 1：下一段从这一刀之后开始。

完整版教学

一、切割型回溯：选择「在哪切」

前面的排列、组合、子集，「选择」都是「挑一个元素放进路径」。分割回文串是另一类——切割问题：把一个序列切成连续的几段。这里每一步的「选择」是「这一刀切在哪个位置」，也就是「当前这段取多长」。

s = "aab" 的答案是 [["a","a","b"], ["aa","b"]]：第一种切成三段、第二种前两个字符合成一段。可以看到，切割方案的本质就是「在字符之间的哪些缝隙下刀」。

二、决策树：切割位置就是分支

以 start 记「当前这段从哪个下标开始切」。站在 start，枚举这一段的终点 end（从 start 到末尾）：

选 end = start：切下单字符 s[start]；
选 end = start+1：切下两个字符的段；
……

每一个 end 就是决策树的一个分支。选定后，下一段的 start 变成 end + 1，递归下去。当 start 恰好越过字符串末尾（start == s.length()），说明整串被不重不漏地切完，路径 path 就是一种合法切法，收集它。

三、剪枝：非回文子串直接跳过

题目要求每段都是回文，这正好是天然的剪枝点：枚举 end 时，只有当 [start, end] 这段是回文，才值得切下并递归；不是回文就直接跳过这个 end，连递归都不进。

这一步把大量无效分支挡在门外——例如 s="abc"，从 start=0 切 [0,1]="ab" 不是回文，就不会去递归「切完 ab 之后的部分」，避免了整棵注定失败的子树。

四、代码与 start 的作用

start 在这里扮演双重角色：既是「当前段的起点」，又充当「切割点不回头」的界定——每段都从上一刀之后接着切，不会重叠、不会遗漏，所以切法不会重复。这和组合/子集里 start 只往后选、避免重复是同一种思想，只不过对象从「选元素」变成了「定切点」。

结束条件 start == s.length() 也和别的题不同：不是「路径长度达到某值」，而是「原串被切割位置推进到了末尾」。

五、优化：预处理回文判断（DP 表）

朴素实现里，每次 isPalindrome(s, start, end) 都要 O(len) 现算，整体偏慢。可以预处理一张回文表 dp[i][j]（表示子串 [i,j] 是否回文），用动态规划 O(n²) 一次性算好：

dp[i][j] = (s[i]==s[j]) && (j-i<2 || dp[i+1][j-1])

之后回溯里判断回文变成 O(1) 查表。这样把「判回文」的重复计算省掉，是这题常见的进阶优化。回溯负责枚举所有切法（本身就是指数级），DP 表只是加速其中的「判回文」子步骤，二者配合。

六、把状态、选择与撤销画成决策树

本题递归状态的精确定义是：start 表示尚未切分的后缀起点，path 中片段均已验证回文；选择 end 就确定下一刀。状态含义越清楚，结束条件、候选范围和去重位置越容易从题意推出。

进入节点：检查当前状态与剩余目标
枚举候选：先判断约束和剪枝条件
做选择：同步修改 path / used / 约束集合
递归下一层
撤销选择：恢复到进入本节点前的状态

带数字推演：aab 在 start=0 可选 a 再选 a,b，也可选 aa 再选 b，得到两种分割。画树时只需展开能体现“同层选择”和“纵向递归”区别的两三层，并标出被剪掉的分支，便能解释去重或剪枝为什么不会漏解。

记忆钩子：回溯不是“递归试一试”，而是维护状态不变量；做选择与撤销必须镜像，剪枝必须证明被删分支不可能产生答案。

七、复杂度、剪枝代价与实现边界

关键实现边界是：预处理 pal[i][j] 可把回文判断从 O(n) 降为 O(1)；空串与单字符边界要统一。回溯复杂度不能只写一个固定模板，应说明树深、每层分支数、合法叶子数以及复制答案的成本。

维度	自检问题
状态	参数能否唯一描述当前节点
候选	是否遗漏合法选择或重复枚举
剪枝	条件是必要条件还是拍脑袋
撤销	path、标记和计数是否全部恢复
输出	保存的是快照还是共享可变引用

测试应包含无解、唯一解、多解、最小规模、全部候选相同或冲突密集的输入。对可变字符串、棋盘和标记数组，还应在递归返回后断言状态与进入前一致；这类断言比只比较最终答案更容易定位撤销错误。

八、常见误区与追问

误区：每个位置只有切或不切所以无需验证片段。 仍需保证每个产生的片段是回文。
误区：发现非回文 end 后可以 break。 更长子串仍可能成为回文，只能 continue。
误区：DP 表改变了回溯树大小。 它主要降低每个候选的回文检查成本。
追问：为什么递归传 end+1？ 下一片必须紧接已选片段，不能重叠或留空。
追问：复杂度怎样估计？ 最坏有 2^(n-1) 种切法，复制结果还包含 O(n) 字符。
追问：如何构造回文表？ 按长度递增，pal[i][j]=s[i]==s[j] 且长度≤2或 pal[i+1][j-1]。

九、加强记忆

分割回文串是切割型回溯：选择不是「选元素」而是「在哪切一刀」——用 start 定段起点，枚举终点 end，只有 [start,end] 回文才切下并递归到 end+1（非回文直接跳过，这是核心剪枝）。start 推进到串末（start==s.length()）收集一种切法。start 兼顾「段起点」和「切点不回头、不重不漏」。优化：用 DP 预处理 dp[i][j] 回文表，把判回文降到 O(1)。

简化版

详细版