今日算法（带回文问题的回溯）

一、题目描述

给你一个字符串s，请你将s分割成一些子串，使每个子串都是回文串。 返回所有可能的分割方案。

示例 1输入：s = "aab"输出：[["a","a","b"],["aa","b"]]

示例 2输入：s = "a"输出：[["a"]]

示例 3输入：s = "aaa"输出：

[ ["a","a","a"], ["a","aa"], ["aa","a"], ["aaa"] ]

二、解法：纯回溯法（最易懂版本）

核心思路（一句话）

在字符串的空隙里尝试 “切一刀”，只要切出来的子串是回文，就继续往下切；直到切完整个字符串，就记录一种方案。

回溯三要素（必背）

1. 选择：从当前位置开始，截取一段子串
2. 限制：截取的子串必须是回文
3. 结束：截取到字符串末尾，记录答案

三、完整代码（C++）

#include <vector> #include <string> using namespace std; class Solution { public: vector<vector<string>> partition(string s) { vector<vector<string>> result; // 存放最终所有答案 vector<string> path; // 存放当前正在分割的方案 backtrack(s, 0, path, result); return result; } private: // 回溯函数 // start: 从哪个下标开始分割 void backtrack(const string& s, int start, vector<string>& path, vector<vector<string>>& result) { // 1. 终止条件：已经分割到字符串末尾 → 记录答案 if (start == s.size()) { result.push_back(path); return; } // 2. 尝试所有可能的分割位置：从 start 开始，到 i 结束 for (int i = start; i < s.size(); ++i) { // 判断 s[start ... i] 是否是回文 if (isPalindrome(s, start, i)) { // 是回文 → 加入当前路径 path.push_back(s.substr(start, i - start + 1)); // 3. 递归：继续分割下一段 backtrack(s, i + 1, path, result); // 4. 回溯：撤销选择 path.pop_back(); } } } // 判断 s[left ... right] 是否是回文串 bool isPalindrome(const string& s, int left, int right) { while (left < right) { if (s[left] != s[right]) return false; left++; right--; } return true; } };

四、代码逐行解释（博客重点）

1. 主函数

backtrack(s, 0, path, result);

• 从下标0开始分割
• path记录当前分割方案
• result收集所有合法答案

2. 终止条件

if (start == s.size())

表示已经把整个字符串分割完成，此时path就是一个合法方案，存入结果。

3. 循环尝试所有分割点

for (int i = start; i < s.size(); i++)

• start：本次分割的起点
• i：本次分割的终点
• 截取子串：s[start ... i]

4. 只选择回文子串

if (isPalindrome(s, start, i))

只有子串是回文，才继续递归。

5. 回溯核心

path.push_back(...) backtrack(...) path.pop_back();

• 先选
• 再递归
• 最后撤销选择，尝试下一种分割方式

五、案例 1：s = "aab" 完整推演（最经典）

字符串：a a b下标：0 1 2

第一层：start = 0

尝试分割：

• [0,0] = "a"✅ 回文
• [0,1] = "aa"✅ 回文
• [0,2] = "aab"❌ 不是回文

分支 1：选 "a" → start = 1

第二层：start = 1

• [1,1] = "a"✅ 回文 → start = 2
  • [2,2] = "b"✅ 回文 → start = 3（结束） → 得到方案：["a","a","b"]

分支 2：选 "aa" → start = 2

第二层：start = 2

• [2,2] = "b"✅ 回文 → start = 3（结束） → 得到方案：["aa","b"]

最终结果

plaintext

[["a","a","b"], ["aa","b"]]

六、案例 2：s = "aaa" 推演（帮你彻底吃透）

所有可能分割：

1. a | a | a
2. a | aa
3. aa | a
4. aaa

回溯过程

1. start=0 选a→ start=1 选a→ start=2 选a✅
2. start=0 选a→ start=1 选aa✅
3. start=0 选aa→ start=2 选a✅
4. start=0 选aaa✅

最终输出 4 种方案。

七、案例 3：s = "ab"

• 尝试[0,0] = "a"→ 剩下[1,1] = "b"→ 得到["a","b"]
• 尝试[0,1] = "ab"❌ 不是回文结果：[["a","b"]]

八、回溯法为什么正确？

1. 不重不漏：枚举所有合法分割点
2. 剪枝：不是回文就直接跳过，不递归
3. 结构清晰：标准回溯模板，面试必背

九、博客总结

• 分割回文串是一道经典回溯题
• 核心：枚举切割点 + 判断回文
• 模板：选择 → 递归 → 撤销选择
• 终止条件：切割到字符串末尾
• 判断回文使用双指针即可