分割回文串：回文才下刀，再切后缀
从当前起点枚举终点，这一段是回文才切一刀，然后对剩下的后缀重复。所有走到底的切法都要。
回溯 dfs(start)：枚举终点 end，若 s[start..end] 是回文，就把这段推进 parts，再 dfs(end+1)；start 走到串尾时拷贝一份 parts 作为方案。不是回文的终点直接跳过。回文判断可以双指针现场做，也可以预处理 dp[i][j]。时间 O(n·2^n)，空间 O(n²)。
这是 LeetCode 131. Palindrome Partitioning。给你字符串 s，把它分割成若干连续子串，使每一段都是回文，返回全部切法。子串必须覆盖 s 且不重叠、不打乱顺序；一段切法里至少有一刀落在每个字符间隙的「切或不切」选择上，但单独一个字符永远是回文，所以至少存在一种「全切成单字符」的方案。
主例 s = "aab"。两种合法切法：["a", "a", "b"] 和 ["aa", "b"]。"ab" 不是回文，不能作为第一段；"aab" 本身也不是回文，不能一刀不切。
枚举所有切法再逐段检查，能做对，但大量前缀已经不是回文的路径还会继续往下切。缺的是：一旦当前这一段不是回文，后面怎么切都救不回来。本文从这一刀的合法性推出回溯：只把回文段推进路径，再对后缀递归。
枚举终点，回文才切
把 s 的 n−1 个间隙看成切或不切，一共 2^{n−1} 种切法。主例 n=3，四种里 "a|ab" 的第二段不是回文，必须丢掉。第一直觉是先切完再验；更好的问法是：已经切出的前缀都合法时，下一刀的终点可以落在哪里。
缺口收成一个带起点的函数 dfs(start)：s[0..start) 已经按 parts 切好且每段都是回文，现在要切 s[start..]。枚举 end 从 start 到 n−1，只有 s[start..end] 是回文才把这段推进 parts，再 dfs(end+1)。start == n 说明整串切完，拷贝 parts 记入答案，然后退刀。不是回文的 end 根本不递归——这条分支没有后缀能补救。
用手走主例，对应五帧。start=0，试 end=0，段 "a" 是回文，切一刀，parts 变成 ["a"]，去处理 "ab"。start=1，试 end=1，段 "a" 是回文，parts 变成 ["a","a"]，去处理 "b"。start=2，试 end=2，段 "b" 是回文，start 走到 3，记方案 ["a","a","b"]。这是演示前三帧。
退回到 start=1，试 end=2，段 "ab" 两端 a≠b，不是回文，剪掉。再退到 start=0，试 end=1，段 "aa" 是回文，切一刀后只剩 "b"，再切得到 ["aa","b"]。最后试 end=2，段 "aab" 不是回文，剪掉。答案就是演示最后一帧的两种方案。
单字符一定回文，所以 dfs 至少能靠「每刀只切一格」走到串尾，不会漏掉全单字符方案。现场判回文是两端往中间夹，一段长度 k 要 O(k)；同一段会被不同前缀路径重复问到，可以先花 O(n²) 预处理 dp[i][j] = s[i]==s[j] && dp[i+1][j−1]，查询变 O(1)。复杂度瓶颈仍在方案数，最坏每个间隙都可切。
为什么非回文段必须剪分割要求每一段都是回文。当前 [start,end] 已经不合法，再怎么切它右边，这一段仍留在方案里。主例的 "ab"、"aab" 都是这样被丢掉的。
Go：回溯分割
func partition(s string) [][]string {res := [][]string{}parts := []string{}n := len(s)var isPal func(int, int) boolisPal = func(l, r int) bool {for l < r {if s[l] != s[r] { return false }l++; r--}return true}var dfs func(int)dfs = func(start int) {if start == n {res = append(res, append([]string{}, parts...))return}for end := start; end < n; end++ {if !isPal(start, end) { continue }parts = append(parts, s[start:end+1])dfs(end + 1)parts = parts[:len(parts)-1]}}dfs(0)return res}
1isPal 两端夹。l≥r 时空段或单字符，直接 true。主例 "ab" 第一对就 false。
2start==n 才记方案。必须拷贝 parts，否则后续退刀会改掉已经记下的切片。
3end 从 start 扫到末尾。不是回文 continue，不递归——主例的 "ab"、"aab" 走这里。
4切一刀后 dfs(end+1) 处理后缀；返回必须把 parts 弹出，否则 ["a","a","b"] 会污染下一条 ["aa","b"]。
总结
从 start 枚举 end，回文才切，再切后缀。主例两种： [a,a,b] 与 [aa,b]。
- 非回文段没有后缀能补救，必须当场剪掉。主例 "ab"、"aab" 都是。
- 单字符恒回文，全切成单字符一定是一种方案。
- 记方案时要拷贝 parts；回文判断可预处理成 dp，查询 O(1)。