Palindrome Partitioning: the idea to remember.

The core insight

At each start position, recurse on every palindromic prefix and restore the current partition afterward.

Why it works

Every valid partition begins with one of those palindromic prefixes, so recursion covers every valid cut sequence.

The mistake to avoid

Single characters are palindromes. Copy the completed partition before backtracking.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

// Java reference adapted from neetcode-gh/leetcode (MIT).
// At each start position, recurse on every palindromic prefix and restore the current partition afterward.
public List<List<String>> partition(String s) {
    List<List<String>> res = new ArrayList<List<String>>();
    if (s.equals("")) {
        res.add(new ArrayList<String>());
        return res;
    }
    for (int i = 0; i < s.length(); i++) {
        if (isPalindrome(s, i + 1)) {
            for (List<String> list : partition(s.substring(i + 1))) {
                list.add(0, s.substring(0, i + 1));
                res.add(list);
            }
        }
    }
    return res;
}

public boolean isPalindrome(String s, int n) {
    for (int i = 0; i < n / 2; i++) {
        if (s.charAt(i) != s.charAt(n - i - 1)) return false;
    }
    return true;
}

Java reference adapted from neetcode-gh/leetcode · MIT license

Make the next connection