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 List<List<String>> partition(String s) {
        List<List<String>> result=new LinkedList<List<String>>();
        LinkedList<String> output=new LinkedList<String>();
        dfs(s,0,output,result);
        return result;
    }
    public void dfs(String s,int start,LinkedList<String> output,List<List<String>> result){
        if(start==s.length()){
            List<String> list=new LinkedList<String>();
            list.addAll(output);
            result.add(list);
            return;
        }
        for(int i=start;i<s.length();i++){
            if(isPalindrome(s,start,i)){
                output.add(s.substring(start,i+1));
                dfs(s,i+1,output,result);
                output.pollLast();
            }
        }
    }
    public boolean isPalindrome(String s,int i,int j){
        while(i<=j){
            if(s.charAt(i)==s.charAt(j)){
                i++;
                j--;
            }
            else return false;
        }
        return true;
    }
}