给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
这是经典的计算机算法问题，通常使用回溯算法来解决。
核心思路：
- 切割问题：我们可以字符串切割想象成一棵树，从字符串的第一个字符开始，尝试切割出不同长度的子串。
- 判断回文：如果当前切割出来的子串是回文串，我们就继续对剩余的字符串进行递归切割
- 终止条件：当切割线移动道字符串的末尾时间，说明我们找到了一组完整的分割方案。
Java代码实现如下：
import java.util.ArrayList;
import java.util.List;class Solution {List<List<String>> res = new ArrayList<>();List<String> path = new ArrayList<>();public List<List<String>> partition(String s) {backtracking(s, 0);return res;}private void backtracking(String s, int startIndex) {// 如果起始位置已经大于等于字符串长度，说明找到了一组方案if (startIndex >= s.length()) {res.add(new ArrayList<>(path));return;}for (int i = startIndex; i < s.length(); i++) {// 如果 [startIndex, i] 是回文串，则记录并继续递归if (isPalindrome(s, startIndex, i)) {String str = s.substring(startIndex, i + 1);path.add(str);} else {continue;}// 递归：寻找 i+1 往后的分割方案backtracking(s, i + 1);// 回溯：撤销本次处理，尝试其他分割点path.remove(path.size() - 1);}}// 双指针法判断回文private boolean isPalindrome(String s, int start, int end) {for (int i = start, j = end; i < j; i++, j--) {if (s.charAt(i) != s.charAt(j)) {return false;}}return true;}
}
关键点解析
回溯逻辑：for循环决定了横向的切割位置，backtracking递归调用决定了纵向的切割深度。
示例执行过程 (s = "aab")
- 第一层：
-
切 "a"：是回文，进入递归。
-
第二层：从剩下 "ab" 中切 "a"：是回文，进入递归。
- 第三层：从剩下 "b" 中切 "b"：是回文，加入结果集 ["a", "a", "b"]。
-
-
切 "aa"：是回文，进入递归。
- 第二层：从剩下 "b" 中切 "b"：是回文，加入结果集 ["aa", "b"]。
-
切 "aab"：不是回文，跳过。