1   public class Solution {
 2     public ArrayList<ArrayList<String>> partition(String s) {
 3         ArrayList<ArrayList<String>> res = new ArrayList<ArrayList<String>>();
 4         if(s.length()<=0){
 5             return res;
 6         }
 7         StringBuilder sb = new StringBuilder();
 8         boolean p[][] = new boolean[s.length()][s.length()];
 9         get(s,p);
10         DFS(s,0,p,new ArrayList<String>(),res);
11         return res;
12     }
13     public void DFS(String s,int start,boolean p[][] ,ArrayList<String> output,ArrayList<ArrayList<String>> res){
14         if(start==s.length()){
15             ArrayList<String> temp = new ArrayList<String>();
16             temp.addAll(output);
17             res.add(temp);
18             return;
19         }
20         for(int i=start;i<s.length();i++){
21             if(p[start][i]){
22                 output.add(s.substring(start,i+1));
23                 DFS(s,i+1,p,output,res);
24                 output.remove(output.size()-1);
25             }
26         }
27     }
28     public void get(String s,boolean [][]p){
29         for(int i=s.length()-1;i>=0;i--){
30             for(int j=i;j<s.length();j++){
31                 if(s.charAt(i)==s.charAt(j)&&(j-i<2||p[i+1][j-1]))
32                     p[i][j]=true;
33             }
34         }
35     }
36 }