1class Solution {2    public List<List<String>> partition(String s) {3        List<List<String>> result = new ArrayList<>();4        search(s, 0, new ArrayList<>(), result);5        return result;6    }7    private void search(String s, int start, List<String> path, List<List<String>> result) {8        if (start == s.length()) {9            result.add(new ArrayList<>(path));10            return;11        }12        for (int end = start; end < s.length(); end++) {13            if (!palindrome(s, start, end)) continue;14            path.add(s.substring(start, end + 1));15            search(s, end + 1, path, result);16            path.remove(path.size() - 1);17        }18    }19    private boolean palindrome(String s, int left, int right) {20        while (left < right) {21            if (s.charAt(left++) != s.charAt(right--)) return false;22        }23        return true;24    }25}