class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        backtrack(res, new ArrayList<String>(), 0, s);
        return res;
    }

    private void backtrack(List<List<String>> res, List<String> path, int index, String s) {
        if (index == s.length()) {
            res.add(new ArrayList<String>(path));
            return;
        }

        for (int i = index; i < s.length(); i++) {
            if (isPalindrome(s.substring(index, i + 1))) {
                path.add(s.substring(index, i + 1));
                backtrack(res, path, i + 1, s);
                path.remove(path.size() - 1);
            }
        }
    }

    private boolean isPalindrome(String s) {
        char[] arr = s.toCharArray();
        int l = 0;
        int r = arr.length - 1;

        while (l < r) {
            if (arr[l] != arr[r]) return false;
            l++;
            r--;
        }

        return true;
    }
}