class Solution {
    /**
            []
           /   \
        "a"     "aa"
       /          \
    "a"            "b"
     |              |
    "b"             END
     |
    END
    */
    
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        List<String> current = new ArrayList<>();

        solve(s, 0, s.length(), result, current);
        return result;
    }

    public void solve(String s, int i, int j, List<List<String>> result, List<String> current)
    {
        // base condition
        if(i == s.length()) {
            result.add(new ArrayList<>(current));
            return;
        }
        // Define k-loop scheme
        for(int k=i; k<=j-1; k++)
        {
            if(isPalindrome(s, i, k))
            {
                // choose
                current.add(s.substring(i, k+1));

                // explore
                solve(s, k+1, j, result, current);

                // un-choose (backtrack)
                current.remove(current.size() - 1);
            }
        }
        return;
    }

    public boolean isPalindrome(String s, int i, int j)
    {
        String s1 = s.substring(i, j+1);
        String s2 = new StringBuilder(s1).reverse().toString();
        
        return s1.equals(s2);
    }
}