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

partition.java

/*
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"]
  ]

*/
public class Solution {
   public ArrayList<ArrayList<String>> partition(String s) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<String> set = new ArrayList<String>();
        StringBuffer tmp = new StringBuffer();
        ArrayList<ArrayList<String>> totalSets = new ArrayList<ArrayList<String>>();

        subset(0, s, set, tmp);
        
        ArrayList<String> paliSet = new ArrayList<String>();
        for(int i = 0; i < set.size(); i++) {
            //System.out.println(set.get(i));
            if(isPalindrome(set.get(i))) {
                paliSet.add(set.get(i));
            }
        }
        // combine all the palidrome to build the original string
        ArrayList<String> tmpSet = new ArrayList<String>();
        combine(totalSets, paliSet, s, tmpSet);
        return totalSets;
    }
    
    public void subset(int start, String str, ArrayList<String> set, StringBuffer tmp) {
        if(start == str.length()) return;
        
        for(int i = start; i < str.length(); i++) {
            // try
            //if(i>0 && str.charAt(i-1) == str.charAt(i)) continue;
            tmp.append(str.charAt(i));
            if(str.indexOf(tmp.toString()) >= 0 && set.indexOf(tmp.toString()) < 0) {
                set.add(tmp.toString());
            }
            // redo
            subset(i+1, str, set, tmp);
            // reverse back
            tmp.deleteCharAt(tmp.length() - 1);
        }
        
        
        return;
    }
    
    public boolean isPalindrome(String str) {
        int size = str.length();
        int left = 0;
        int right = size - 1;
        if(size == 1) return true;
        while(left < right) {
            if(str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
    
    public void combine(ArrayList<ArrayList<String>> totalSets, ArrayList<String> set, String str, ArrayList<String> tmpSet) {
        // combine all the subset to become the original string
        int size = set.size();
        if(str.length() == 0) {
            totalSets.add(new ArrayList<String>(tmpSet));
        }
        for(int i = 0; i < size; i++) {
            if(str.indexOf(set.get(i)) == 0) {
                // try
                String tmp = set.get(i);
                tmpSet.add(tmp);
                combine(totalSets, set, str.substring(tmp.length(), str.length()), tmpSet);
                // redo
                tmpSet.remove(tmpSet.size() - 1);
            }
        }
        return;
    }

  }