Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",

Return

[    ["aa","b"],    ["a","a","b"]  ] 回溯算法，需要注意的就是在得到子串时判断是否为回文字符串（需要自己写函数），如果是才继续展开下一层。 代码：

1 public List
     
      
       > partition(String s) { 2         List
       
        
         > re = new ArrayList
         
          
           >(); 3 if(s==null || s.length()==0) 4 return re; 5 List
           
             path = new ArrayList
            
             (); 6 collect(re, path, s, 0); 7 return re; 8 } 9 public void collect(List
             
              
               > re, List
               
                 path, String s, int start)10 {11 for(int i=start+1;i<=s.length();i++)12 {13 String temp = s.substring(start,i);14 if(!isP(temp))15 continue;16 path.add(temp);17 if(i==s.length())18 re.add(new ArrayList
                
                 (path));19 else20 collect(re, path, s, i);21 path.remove(path.size()-1);22 }23 }24 public boolean isP(String x)25 {26 int p = 0;27 int q = x.length()-1;28 while(p