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

Return all possible palindrome partitioning of s.

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        if(s == null || s.length() == 0)
            return res;

        helper(res, new ArrayList<String>(), 0, s);

        return res;
    }

    public void helper(List<List<String>> res, List<String> line, int start, String s) {
        if(start == s.length()) {
            res.add(new ArrayList<String>(line));
            return;
        }

        for(int i = start + 1; i <= s.length(); i++) {
            if(isPalindrome(s.substring(start, i).toCharArray())) {
                line.add(s.substring(start, i));
                helper(res, line, i, s);
                line.remove(line.size() - 1);
            }
        }
    }

    public boolean isPalindrome(char[] cs) {
        int i = 0;
        int j = cs.length - 1;
        while(i < j) {
            if(cs[i] != cs[j])
                return false;
            i++;
            j--;
        }

        return true;
    }
}