分割回文串
Palindrome Partitioning
把字符串切分成若干段，使每一段都是回文；返回所有切分方案。
在力扣中练习题目描述
给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
示例 1：
输入：s = "aab" 输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a" 输出：[["a"]]
提示：
1 <= s.length <= 16s仅由小写英文字母组成
解题思路
主解法
回溯 · 枚举切点
从 start 枚举 end，是回文才切，切完递归
在位置 start 上，下一段的结束位置 end 可以取 start..n-1。只有 s[start..end] 是回文时，才把它加入 path 并递归到 end+1。
因为每次都从 start 往后枚举，切分不会重复，也不会漏掉“整段就是一个回文”的情况。
分步图解
从 start 开始枚举切点 end；只有 s[start..end] 是回文，才切下这一段并递归。
自拟串 "abba" 有三种切法：单字符、中间 bb 成段、整段 abba。中间的 "ab"、"abb" 不是回文，会被直接跳过。
分步图解
s[0..0] = "a" 是回文，切下它并递归。
- start
- 1
最坏情况下每个位置都可以切，方案数是指数级；总时间 O(n·2ⁿ)，递归深度 O(n)。
时间 O(n·2ⁿ)空间 O(n)
易错点
- 只按固定长度切：会漏掉不同长度的回文段。
- 忘记 isPal 检查：把任意子串都当成回文。
- 递归传 start+1：每次都只切一个字符，得不到 bb/abba。
- 收集时没有复制 path：后续撤销会污染结果。
代码与演示
演示输入
s = "abba"从 start 开始枚举切点 end；只有 s[start..end] 是回文，才切下这一段并递归。
查看 C++ 代码
延伸阅读
- 回文判断可以预处理成 O(n²) 的布尔表，让每次查询 O(1)；字符串很长时值得。
- 本题与“单词拆分”结构相似：都是枚举下一段，只是一个要求回文，一个要求字典命中。