回溯算法 递归，把大问题分解成小问题，子问题
class Solution { private boolean check(String s) { int l=0,r=s.length()-1; while(l<r) { if(s.charAt(l)!=s.charAt(r)) { return false; } l++; r--; } return true; } private void backTrack(List<List<String>> res,String s,ArrayList<String> tmp) { if(s==null||s.length()==0) res.add(new ArrayList<>(tmp)); for(int i=1;i<=s.length();++i) { String temp = s.substring(0,i); if(check(temp)) { tmp.add(temp); backTrack(res, s.substring(i,s.length()), tmp); tmp.remove(tmp.size()-1); } } } public List<List<String>> partition(String s) { List<List<String>> res = new LinkedList(); backTrack(res, s, new ArrayList<>()); return res; } }把字符串每次分成两部分 左边部分和右边部分 如果左边是回文，那么探索右边 同时重复这个步骤
举例： 先定住 a不动，看 ab是不是回文 递归到下一次 又定住 a不动，看b是不是回文 于是 得到 [a,a,b] 的结果 回溯到上一层 定住 aa不动，看b是不是回文 是! 得到 [aa,b] 回溯到上层 定住 aab,很明显不是回文，于是过程完成，结束
