好的！我们详细分析 partition("aab") 的 完整回溯过程，包括每次的递归调用、回溯操作以及 path 的变化情况。
代码
class Solution {public:vector<vector<string>> ans; // 存储最终结果vector<string> path; // 记录当前回文分割路径// 判断 s[left:right] 是否是回文bool isPalindrome(string& s, int left, int right) {while (left < right) {if (s[left++] != s[right--]) {return false;}}return true;}// 递归回溯函数void dfs(string& s, int i) {if (i == s.size()) { // 遍历到字符串末尾，存储当前路径ans.emplace_back(path);return;}for (int j = i; j < s.size(); j++) { // 遍历 s[i:n] 可能的回文子串if (isPalindrome(s, i, j)) { // 如果 s[i:j] 是回文path.push_back(s.substr(i, j - i + 1)); // 选择该子串dfs(s, j + 1); // 递归搜索剩余部分path.pop_back(); // 回溯，撤销选择}}}vector<vector<string>> partition(string s) {ans.clear();path.clear();dfs(s, 0); // 从第 0 个字符开始递归return ans;}};输入
string s = "aab";
Solution sol;
vector<vector<string>> result = sol.partition(s);
完整运行步骤
初始状态：
s = "aab"
path = []
第一步：从 s[0] 开始尝试所有可能的回文前缀
遍历 i = 0 到 n-1，寻找所有 s[0:j] 是回文的情况。
i j s[i:j] 是否回文 path
0 0 "a" ✅ 是回文 ["a"]
0 1 "aa" ✅ 是回文 ["aa"]
0 2 "aab" ❌ 不是回文 ——
第二步：选择 "a" 作为第一个子串，递归继续
path = ["a"]
dfs(s, 1) // 继续递归，处理 s[1:]
遍历 i = 1 到 n-1，寻找所有 s[1:j] 是回文的情况。
i j s[i:j] 是否回文 path
1 1 "a" ✅ 是回文 ["a", "a"]
1 2 "ab" ❌ 不是回文 ——
第三步：选择 "a" 作为第二个子串，递归继续
path = ["a", "a"]
dfs(s, 2) // 继续递归，处理 s[2:]
遍历 i = 2 到 n-1，寻找所有 s[2:j] 是回文的情况。
i j s[i:j] 是否回文 path
2 2 "b" ✅ 是回文 ["a", "a", "b"]
到达字符串末尾 i = 3，存储当前路径：
ans = [["a", "a", "b"]]
回溯：撤销 "b"
path = ["a", "a"]
第四步：回溯到 "a"，尝试 "aa"
回溯：撤销 "a"
path = ["a"]
选择 "aa" 作为第一个子串：
path = ["aa"]
dfs(s, 2) // 继续递归，处理 s[2:]
遍历 i = 2 到 n-1，寻找所有 s[2:j] 是回文的情况。
i j s[i:j] 是否回文 path
2 2 "b" ✅ 是回文 ["aa", "b"]
到达字符串末尾 i = 3，存储当前路径：
ans = [["a", "a", "b"], ["aa", "b"]]
回溯：撤销 "b"
path = ["aa"]
第五步：回溯到初始状态
回溯：撤销 "aa"
path = []
尝试 "aab"：
path = ["aab"]
i j s[i:j] 是否回文 path
0 2 "aab" ❌ 不是回文 ——
无法继续，回溯结束。
最终输出
[
["a", "a", "b"],
["aa", "b"]
]
完整回溯树
""
/ \
"a" "aa"
/ \
"a" "b"
/ \
"b" X
|
X
时间复杂度分析
• 检查子串是否是回文 需要 O(n^2)。
• 递归搜索所有分割方案 需要 O(2^n)。
总时间复杂度：O(n * 2^n)。
总结
✅ 核心思想
• 回溯 + 递归 生成所有可能的子串组合。
• 剪枝优化：非回文串不进行递归。
