public List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<>();
List<String> palindromes = new ArrayList<>();
getPartitions(0, s, palindromes, res);
public void getPartitions(int index, String s, List<String> palindromes, List<List<String>> res) {
if (index == s.length()) {
res.add(new ArrayList<>(palindromes));
for (int i = index; i < s.length(); i++) {
if (isPalindrome(s, index, i)) {
palindromes.add(s.substring(index, i + 1));
getPartitions(i + 1, s, palindromes, res);
palindromes.remove(palindromes.size() - 1);
public boolean isPalindrome(String s, int start, int end) {
if (s.charAt(start) != s.charAt(end)) {