我對(duì)回溯題還是不清楚，尤其是還原現(xiàn)場(chǎng)這部分。
這道題是從答案角度出發(fā)，考慮如何分割。參考Leetcode的解題。

在這個(gè)回溯過程中：

1. 每走一步，對(duì)于每個(gè)逗號(hào)，有兩個(gè)選項(xiàng)：要么不選它，要么選它。每個(gè)選項(xiàng)就像是在樹上走一個(gè)分支。
2. 但是我們一次只能處理一個(gè)分支，計(jì)算完了【不選】的分支，就要倒回去，回到前面去處理另外一個(gè)【選】的分支。倒回去之前加到 path 中的數(shù)據(jù)是垃圾數(shù)據(jù)，要及時(shí)清除掉。

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);return ans;}private void dfs(int i){if(i==s.length()){ans.add(new ArrayList<>(path));return;}//i為子串開始的位置，j為子串結(jié)束的位置for(int j=i; j<s.length();j++){if(isPalindrome(i,j)){path.add(s.substring(i,j+1));//對(duì)s的剩余部分進(jìn)行分割dfs(j+1);//回溯path.remove(path.size()-1);}}}//判斷是否為回文串private boolean isPalindrome(int left, int right){while(left<right){if(s.charAt(left++)!=s.charAt(right--)){return false;}}return true;}
}