題目：

給你一個字符串?s，請你將?s?分割成一些子串，使每個子串都是?回文串?。返回?s?所有可能的分割方案。

回文串?是正著讀和反著讀都一樣的字符串。

方法：靈神-子集型回溯

假設每對相鄰字符之間有個逗號，那么就看每個逗號是選還是不選。

也可以理解成：是否要把?s[i]s[i]s[i]?當成分割出的子串的最后一個字符。

代碼：

class Solution {private final List<List<String>> ans = new ArrayList<>();private final List<String> path = new ArrayList<>();private String s;public List<List<String>> partition(String s) {this.s = s;dfs(0, 0);return ans;}private boolean isPalindrome(int left, int right) {while (left < right) {if (s.charAt(left++) != s.charAt(right--))return false;}return true;}// start 表示當前這段回文子串的開始位置private void dfs(int i, int start) {if (i == s.length()) {ans.add(new ArrayList<>(path));return;}// 不選 i 和 i + 1 之間的逗號（i = n - 1 時一定要選）if (i < s.length() - 1)dfs(i + 1, start);// 選 i 和 i + 1 之間的逗號（把 s[i] 作為子串的最后一個字符）if (isPalindrome(start, i)) {path.add(s.substring(start, i + 1));dfs(i + 1, i + 1);              // 下一個子串從 i+1 開始path.remove(path.size() - 1);   // 恢復現場}}
}