A puzzle feature splits a product slug into palindromic tokens and lists every legal cut. The intern placed or skipped a cut in every gap, then checked each piece. "aab" returned two lists. A twenty-letter all-a slug is 2^19 partitions, most of them already illegal after the first mismatched slice.

Return every partition of s into contiguous palindromic substrings. The cuts already sit in s. Rearranging letters is a different prompt; finding one longest palindromic window is a different prompt.

This is an interview writeup, not a backtracking lecture. The backtracking post owns choose-recurse-undo. Here we only care about which end indexes are legal so a non-palindromic prefix never descends.

The problem

Given a String s, return all partitions such that every substring in the partition is a palindrome. Slice order is left to right in s. A single character is a palindrome, so there is always at least one partition.

s = "aab"  →  [["a","a","b"], ["aa","b"]]
s = "a"    →  [["a"]]

Note: Longest Palindromic Substring finds one window. This prompt enumerates every way to cut s so each piece is a palindrome. Valid Palindrome is a filtered phrase — skip punctuation, fold case, then yes or no. Do not recycle either proof.

Every cut pattern is the honest brute force

Between n characters sit n − 1 gaps. Each gap is a cut or not: 2^{n−1} partitions. Split, then two-pointer-test every piece. Correct. Exponential even before the palindrome scans, and illegal prefixes still walk to the end.

List<List<String>> partitionNested(String s) {
    List<List<String>> out = new ArrayList<>();
    generate(s, 0, new ArrayList<>(), out);
    return out;
}

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

allPalindromes runs the two-pointer helper below on every piece. At n = 4 this is a rounding error. At a twenty-letter slug you paid a full tree for a question prune answers on the first non-palindrome: cut only when the prefix is already a palindrome.

Backtrack from the start index

State is a start index: the suffix still to cut. For each end in start .. n-1, if s[start..end] is a palindrome, append the slice, recurse at end + 1, pop. When start == n, the path is complete — copy it out.

The palindrome test is two pointers on that slice: the same meet-in-the-middle as Valid Palindrome without skip-and-fold, and the same character-pair idea Longest Palindromic Substring uses when it expands a center. Here the window is given; you only ask yes or no.

Walk "aab":

s = a a b
    0 1 2

start=0
  end=0  "a" palindrome
    path=["a"]  start=1
      end=1  "a" palindrome
        path=["a","a"]  start=2
          end=2  "b" palindrome
            path=["a","a","b"]  start=3  record
          pop "b"
      pop "a"
      end=2  "ab" not palindrome
    pop "a"
  end=1  "aa" palindrome
    path=["aa"]  start=2
      end=2  "b" palindrome
        path=["aa","b"]  start=3  record
      pop "b"
    pop "aa"
  end=2  "aab" not palindrome

[["a","a","b"], ["aa","b"]]

The Java is that walk:

List<List<String>> partition(String s) {
    List<List<String>> out = new ArrayList<>();
    backtrack(s, 0, new ArrayList<>(), out);
    return out;
}

void backtrack(String s, int start, List<String> path, List<List<String>> out) {
    if (start == s.length()) {
        out.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, out);
            path.remove(path.size() - 1);
        }
    }
}

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

Time is O(n · 2^n) in the worst case — every substring a palindrome, 2^{n−1} leaves, each check and copy linear in n. Extra space is O(n) for the path and the call stack, besides the output.

Note: out.add(path) aliases the live list. Later pops empty every recorded partition. Forget the pop and every sibling inherits a slice it did not choose.

What interviewers usually poke next

  • Min cuts. Palindrome Partitioning II wants the fewest cuts, not the lists. That is DP on this search tree, not this enumeration.
  • Precompute palindromes. A boolean pal[i][j] makes the prefix test O(1). Same exponential partitions; the two-pointer check no longer sits in the inner loop. Usual board answer still starts with the live check.
  • All the same letter. "aaa" yields every cut pattern. Do not claim polynomial time. Constraints around n ≤ 16 are why enumerate is acceptable.
  • Null. Production would reject. At the board, ask.

You are done with this problem when you can say, out loud, why every cut pattern is correct and exponential, why you only recurse when s[start..end] is already a palindrome, and why the pop is what keeps sibling branches honest.