public ArrayList<ArrayList<String>> partition(String s) {
            ArrayList<ArrayList<String>> ans = cache.get(s);
            if (ans != null) {
                return ans;
            }
            ans = new ArrayList<ArrayList<String>>();
            for (int i = 1; i < s.length(); i++) {
                String prefix = s.substring(0, i);
                if (isPalindromic(prefix)) {
                    for (ArrayList<String> subans : partition(s.substring(i))) {
                        ArrayList<String> temp = new ArrayList<String>();
                        temp.add(prefix);
                        temp.addAll(subans);
                        ans.add(temp);
                    }
                }
            }
            if (isPalindromic(s)) {
                ArrayList<String> temp = new ArrayList<String>();
                temp.add(s);
                ans.add(temp);
            }
            cache.put(s, ans);
            return ans;
        }