119. Palindrome Partitioning

Try every possible first cut. If the prefix s[start..end] is a palindrome, keep it and recursively partition the rest. A full partition is complete when start reaches the end of the string.

The choice at each step

Starting at index start, choose where the next palindrome ends. For every end >= start, if s[start..end] is a palindrome, take it as one piece and recurse from end + 1. When start == len(s), the current list of pieces is a valid partition.

Walk-through

backtrack(start, path):
    if start == n: record path; return
    for end in [start, n):
        if s[start..end] is a palindrome:
            path.append(s[start..end])
            backtrack(end + 1, path)
            path.pop()

Worked example

s = "aab":

• Cut a | then a | then b → ["a","a","b"] ✓
• Cut aa | then b → ["aa","b"] ✓
• Cut aab? not a palindrome → rejected.

Result: [["a","a","b"],["aa","b"]].

Complexity

• Time: O(n · 2^n) — up to 2^(n-1) partitions, each checked/copied in O(n).
• Space: O(n) recursion depth (excluding output).

import java.util.ArrayList;
import java.util.List;

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

    private void backtrack(String s, int start, List<String> path, List<List<String>> res) {
        if (start == s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int end = start; end < s.length(); end++) {
            if (isPalindrome(s, start, end)) {
                path.add(s.substring(start, end + 1));
                backtrack(s, end + 1, path, res);
                path.remove(path.size() - 1);
            }
        }
    }

    private boolean isPalindrome(String s, int l, int r) {
        while (l < r) {
            if (s.charAt(l) != s.charAt(r)) return false;
            l++;
            r--;
        }
        return true;
    }
}