分割回文串 · 切刀 + path 栈 + 回溯撤销

把"分割字符串"看作每一刀都要让左侧那一段是回文，回到上一层就把刚才那一刀撤掉。

题目给一个字符串 s = "aab"，要列出所有能让每段都是回文的切法。本页要让你看清楚三件事：切刀如何在 [start..end] 上枚举；path 栈如何 push / pop 严格成对维护；以及 start==len(s) 这一刻为什么 path 就是一个合法答案。

切刀模型path 栈 / 回溯区间 DP 可优化

不预处理回文（朴素版）

时间 · O(n · 2ⁿ) × O(n) 回文判定 = O(n² · 2ⁿ)

空间 · O(n) · 递归栈 + path

区间 DP 预处理回文

时间 · O(n²) 预处理 + O(n · 2ⁿ) 枚举

空间 · O(n²) · DP 表 + O(n) · 路径

为什么是指数级？合法分割方案数本身可能达到 2^(n-1) 量级（每个相邻字符之间都可以选择"切 / 不切"），所以仅"枚举所有合法答案"这一步就已经是指数级的下界。回文判断只是一个常数 / 多项式因子。

边界用例 · 切换后整段动画会重算

帧 1/30Scene 1开场

字符串轨道s = "aab"

递归选择树层 depth · 边 = s[from..to]

活跃节点 / 边收集叶（start==n）剪枝边（非回文）已访问

状态面板

start

end

—

candidate

—

isPalindrome

—

path · 栈top=0

[] 空栈

ans · 结果集len=0

尚无答案

当前步骤

Scene 1：手里是 s = "aab"，要切成全回文段

这道题要把字符串 s = "aab" 切成若干段，每一段都必须是回文。直觉上就是带着一把切刀，从最左边出发，每一刀都要让左侧的那一段是回文。这里 start 指针记录"还没被切的最左字符"，path 是已经切下的回文段栈，ans 收集所有合法切法。

s = "aab" · n = 3

Go 代码 · 三件套核心：push / dfs / pop

1func partition(s string) [][]string {
2    var ans [][]string
3    var path []string
4    var dfs func(start int)
5    dfs = func(start int) {
6        if start == len(s) {
7            tmp := make([]string, len(path))
8            copy(tmp, path)        // 必须拷贝，避免被后续 pop 反污染
9            ans = append(ans, tmp)
10            return
11        }
12        for end := start; end < len(s); end++ {
13            if !isPalindrome(s, start, end) {
14                continue           // 非回文，剪掉这一刀
15            }
16            path = append(path, s[start:end+1])   // ← 落刀 push
17            dfs(end + 1)                          // ← 递归剩余
18            path = path[:len(path)-1]             // ← 撤刀 pop
19        }
20    }
21    dfs(0)
22    return ans
23}
24 
25func isPalindrome(s string, l, r int) bool {
26    for l < r {
27        if s[l] != s[r] {
28            return false
29        }
30        l++
31        r--
32    }
33    return true
34}

不变量 · 为什么这个回溯一定对

· path 中每一段都已经被回文校验通过，向下递归时这条性质继续成立。
· start 之前的字符已经合法切完，剩余待处理串就是 s[start:]。
· 每一层从 start 出发枚举全部回文前缀，既不漏切，也不重复（兄弟分支彼此互斥）。
· push 与 pop严格成对：函数返回时 path 恢复到入口时的样子。
· 当 start == len(s)，path 是一种完整的合法分割，拷贝一份加入 ans。

常见错误 · 别在这里崩盘