解法一：回溯法+动态规划法

回溯法：

• 假设我们当前搜索到字符串的第 i 个字符，且 s[0…i−1] 位置的所有字符已经被分割成若干个回文串，并且分割结果被放入了答案数组 ans 中，那么我们就需要枚举下一个回文串的右边界 j，使得 s[i…j] 是一个回文串。
• 因此，我们可以从 i 开始，从小到大依次枚举 j。对于当前枚举的 j 值，我们使用双指针的方法判断 s[i…j] 是否为回文串：如果 s[i…j] 是回文串，那么就将其加入答案数组 ans 中，并以 j+1 作为新的 i 进行下一层搜索，并在未来的回溯时将 s[i…j] 从 ans 中移除。
• 如果我们已经搜索完了字符串的最后一个字符，那么就找到了一种满足要求的分割方法。

动态规划法：

• 将字符串 s 的每个子串 s[i…j] 是否为回文串预处理出来，使用动态规划即可。设 f(i,j) 表示 s[i…j] 是否为回文串，那么有状态转移方程：
  

class Solution {List<List<String>> result = new ArrayList<List<String>>();List<String> temp = new ArrayList<String>();boolean[][] huiwen;int n;public List<List<String>> partition(String s) {// 初始化n = s.length();huiwen = new boolean[n][n]; // huiwen[i][j]用于记录s[i...j]是否是回文串// 让i<j时，huiwen[i][j]=true，确保huiwen[i+1][j-1]的计算for(int i=0; i<n; i++){Arrays.fill(huiwen[i], true);}for(int i=n-1; i>=0; i--){for(int j=i+1; j<n; j++){ //不能为j=i,否则不为子串huiwen[i][j] = (s.charAt(i)==s.charAt(j)) && huiwen[i+1][j-1];}}backtrace(s, 0);return result;}public void backtrace(String s, int num){// num表示处理到s的第几个数if(num==n){result.add(new ArrayList<String>(temp));return;}for(int j=num; j<n; j++){// num,j表示s[num...j]if(huiwen[num][j]){temp.add(s.substring(num, j+1));backtrace(s, j+1);temp.remove(temp.size()-1);}}}
}

注意：

• 让i<j时，huiwen[i][j]=true，确保huiwen[i+1][j-1]的计算
• 在设置huiwen[i][j] = (s.charAt(i)==s.charAt(j)) && huiwen[i+1][j-1]时，j要从i+1开始，不能为j=i，否则不为子串
• 在回溯的for循环中，num,j表示子串s[num...j]