Hot 100 又来一道标准回溯题，名字听着像文艺片，做起来像切西瓜：
把字符串切成若干段，并且每一段都得是回文串。
这题不难，但很适合拿来练“回溯到底在搜什么”。 你要搜的不是某个最优值，而是：
- 当前这一段从哪里开始
- 这一刀切在哪里结束
- 切出来的这一段是不是回文
只要这三件事理清楚，代码就不会写成一锅回文粥。
题目链接
题目描述
给你一个字符串 s，请你将 s 分割成一些子串，使得每个子串都是回文串，返回 s 所有可能的分割方案。
解题思路：回溯枚举每一段的结束位置
这题最自然的想法就是：
- 当前从位置
start开始切 - 枚举这一段可以在哪个位置
end结束 - 如果
s[start:end+1]是回文串，就把它加入路径 - 然后递归处理后面的部分
当 start == len(s) 的时候，说明整个字符串已经被切完，当前路径就是一种合法答案。
一句话总结它的灵魂：
从左到右切，每次只要当前这段是回文，就递归去切后面。
为什么这是回溯
因为每次做选择时，你都在决定：
- 当前这一段到底切多长
比如字符串 aab：
从下标 0 开始时，可以尝试：
aaaaab
其中：
a是回文，可以继续aa也是回文，也可以继续aab不是回文，直接跳过
于是搜索树就长这样：
start=0├── "a"│ └── start=1│ ├── "a"│ │ └── start=2│ │ └── "b" → ["a", "a", "b"]│ └── "ab" ×└── "aa" └── start=2 └── "b" → ["aa", "b"]所以最后答案就是：
[["a", "a", "b"], ["aa", "b"]]代码实现
class Solution(object): def partition(self, s): """ :type s: str :rtype: List[List[str]] """ n = len(s) ans = [] path = []
def is_pal(sub): return sub == sub[::-1]
def dfs(start): if start == n: ans.append(path[:]) return
for end in range(start, n): if is_pal(s[start:end + 1]): path.append(s[start:end + 1]) dfs(end + 1) path.pop()
dfs(0) return ans代码拆解
1. dfs(start) 表示什么
这里的 start 表示：
当前这一段从哪个位置开始切。
比如 start = 2，就意味着前面的部分已经处理完了，现在只需要考虑 s[2:] 怎么切。
2. 为什么 start == n 就可以加入答案
if start == n: ans.append(path[:]) return当 start 走到字符串末尾时，说明整个字符串已经被完整分割，且前面加入 path 的每一段都经过了回文校验。
所以当前路径就是一种合法方案。
3. 为什么要枚举 end
for end in range(start, n):因为当前这一段可能是：
- 一个字符
- 两个字符
- 三个字符
- ……
- 一直到字符串末尾
也就是说，我们在尝试“这一刀到底切到哪里”。
4. 只有是回文才继续递归
if is_pal(s[start:end + 1]): path.append(s[start:end + 1]) dfs(end + 1) path.pop()这是整题的门槛。
如果当前这一段不是回文，那这条路就没必要继续走了，直接剪掉。
如果是回文：
- 加入当前路径
- 递归处理下一段
- 回溯撤销选择
标准回溯三连，稳得像老油条。
你的“切 / 不切”思路也能做
有些人会写成：
- 遍历到位置
i - 选择“在这里切一刀”
- 或者“先不切，继续往后延长当前段”
这也没问题，本质上还是在枚举切割方案。
不过在表达上，通常“枚举当前段结束位置”会更清晰，因为：
- 状态更直接
- 边界更好理解
- 代码结构也更标准
所以写题解时，更推荐上面那版。
复杂度分析
时间复杂度
这题需要枚举所有可能的分割方案，而一个字符串的切分方式本身就是指数级的。
因此时间复杂度通常可以写为：
O(n * 2^n)其中额外的 n 来自回文判断和路径构造。
空间复杂度
递归栈深度最多为 n，路径长度最多也为 n，所以空间复杂度为：
O(n)如果把结果数组也算上，那最终空间还要加上答案本身的总规模。
可以怎么优化
上面代码里，每次都用：
sub == sub[::-1]来判断回文，写起来很舒服，但会重复计算。
如果想进一步优化，可以先用 dp[i][j] 预处理：
dp[i][j] = True表示s[i:j+1]是回文串
这样回溯时就能 O(1) 判断当前子串是否为回文。
不过这题在面试或刷题场景里，先把基础回溯写对更重要，别还没切瓜，先把菜板升级成 CNC 机床了。
易错点总结
1. 终止条件写错
有些人会把终止条件写成“枚举到最后一个字符”。
其实更准确的是：
当起点
start走到字符串末尾时，说明整个分割完成。
2. 回文判断通过后忘记回溯
path.append(...)dfs(...)path.pop()这一进一出必须成对出现，不然路径会串味，前面切的瓜会混进后面的果盘。
3. 空字符串返回值写错
如果你特地处理空串，也应该返回列表类型：
return []不要返回 False，题目没让你演真假美猴王。
小结
这题的核心非常纯粹：
回溯枚举每一段的结束位置，只要当前子串是回文，就继续切后面的部分。
所以整题就是两步：
- 枚举这一段切到哪里
- 判断这一段是不是回文
只要当前段合法，就递归； 走到字符串末尾，就收集答案。
这就是 131 题的全部秘密。
别看题目叫“分割回文串”，本质上就是一句话：
刀法要稳，切的每一块都得左右对称。 🦐