Difficulty: MediumBacktracking

Palindrome Partitioning

Problem in Plain English

Given a string s, return every way to cut it so each piece is a palindrome that reads the same forwards and backwards. Single characters always qualify, so an answer always exists.

Problem Statement

Given a string s, cut it into pieces so that every piece reads the same forwards and backwards.

Return all possible ways to cut the string that achieve this, where each way is a list of its palindromic pieces.

A single character always counts as a palindrome, so at least one partitioning always exists.

Constraints

1 <= s.length <= 16
s consists of lowercase English letters.

Examples

Example 1

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

The valid cuts give ["a","a","b"] and ["aa","b"]. Keeping "ab" or "aab" as a piece fails because their ends differ. These exhaust the four cut patterns.

Example 2

Input: s = "a"
Output: [["a"]]

The lone character is a palindrome by itself.

Example 3

Input: s = "aba"
Output: [["a","b","a"],["aba"]]

Both all-single-character pieces and the uncut string are valid. The cuts giving ["a","ba"] and ["ab","a"] fail. A longer prefix can be palindromic even when a shorter prefix is not.

Intuition

Each answer chooses cuts between characters, with no gaps or overlaps. For "aab", choosing "a" leaves "ab", which must split again; choosing "aa" leaves "b". Backtracking means append one valid piece, explore the remaining suffix, then remove the piece before trying another end. A palindrome table can answer whether a proposed piece is valid before the search enters that branch.

Approaches

Cut Enumeration

Solution Details

Reveal Cut Enumeration: intuition, complexity, and code

Intuition

Between the n characters sit n - 1 gaps, and each gap is either cut or kept, so every partitioning matches one binary mask. Trying all two to the n minus one masks and checking each piece from both ends cannot miss a valid split.

Step-by-Step Logic

Enumerate every binary mask over the n - 1 gaps. Bit i means cut after character i. For Example 1, n = 3 gives masks 00, 01, 10, 11 in numeric order.
Scan the gaps with start initially 0. At a set bit, copy s[start:i + 1] into parts and move start to i + 1. Always append the final suffix, even when no bit was set.
For each completed piece, compare its left and right characters while moving inward. Reject the mask on the first mismatch. Masks 00 and 01 fail on "aab" and "ab" respectively.
Keep the freshly constructed parts list when every piece passes. Mask 10 records ["aa","b"]; mask 11 records ["a","a","b"]. Return these two lists in any order.

Why It Works

There are n - 1 gaps and each is either cut or uncut, so masks are in one-to-one correspondence with partitions of the whole string into nonempty consecutive pieces. The loop constructs exactly the pieces described by a mask. Comparing symmetric characters is necessary and sufficient for each piece to be a palindrome. Accepting only when every piece passes gives exactly the valid partitions, once each; the single-character partition guarantees at least one answer.

Dry Run

Cut Enumeration: variable states at each step
mask (bit 1, bit 0)	gap actions / start	parts	symmetric checks	result
00	no cut; start stays 0	["aab"]	lo=0, hi=2: a differs from b	[]
01	cut i=0: start 0 to 1; append suffix	["a","ab"]	a: lo=hi=0 passes; ab: lo=0,hi=1 mismatch	[]
10	cut i=1: start 0 to 2; append suffix	["aa","b"]	aa: (0,1) matches then (1,0) stops; b passes	[["aa","b"]]
11	cut i=0: start 0 to 1; cut i=1: start 1 to 2	["a","a","b"]	all single-character pieces pass	[["aa","b"],["a","a","b"]]
done	every mask examined	return in any order	same two partitions as Example 1	[["aa","b"],["a","a","b"]]

Complexity Analysis

Time Complexity

O(n \cdot 2^n)

Space Complexity

O(n+L)

Let n be the string length and L the total stored character data plus list entries in returned partitions. Each of the 2^(n-1) masks scans n - 1 gaps. Its copied pieces together contain n characters, and palindrome scans inspect at most n characters in total, not n per piece. Thus worst-case time is O(n times 2^n). One temporary partition uses O(n); output uses O(L), with L = O(n times 2^n) in the all-equal worst case. Auxiliary space excluding the return is O(n). Substring copying is charged conservatively in all languages.

Code

Solution.java

1import java.util.*;2
3class Solution {4    public List<List<String>> partition(String s) {5        List<List<String>> res = new ArrayList<>();6        int n = s.length();7        // Each bit chooses one gap; n <= 16 keeps the mask within integer range.8        for (int mask = 0; mask < (1 << (n - 1)); mask++) {9            List<String> parts = new ArrayList<>();10            int start = 0;11            for (int i = 0; i < n - 1; i++) {12                if ((mask & (1 << i)) != 0) {13                    parts.add(s.substring(start, i + 1));14                    start = i + 1;15                }16            }17            parts.add(s.substring(start));18            boolean ok = true;19            for (String p : parts) {20                if (!isPalindrome(p)) {21                    ok = false;22                    break;23                }24            }25            if (ok) res.add(parts);26        }27        return res;28    }29
30    private boolean isPalindrome(String p) {31        int lo = 0, hi = p.length() - 1;32        while (lo < hi) {33            if (p.charAt(lo++) != p.charAt(hi--)) return false;34        }35        return true;36    }37}

Hints

Hint 1

Think of every gap as a cut-or-keep decision. Pieces must cover the whole string in order.

Hint 2

At a suffix start, try each possible end and recurse only when that whole piece is palindromic. A failed shorter piece does not justify abandoning longer ends.

Hint 3

Precompute pal[i][j] from matching ends and the inner substring, then append, recurse from j + 1, and pop.

Edge Cases

A single character returns exactly one one-piece partition; there are no gaps to mask.
All equal characters make every one of the 2^(n-1) cut patterns valid; at n = 16 this is 32768 answers.
A string such as "abc" with no longer palindromes has only the all-single-character answer.
Odd palindromes such as "aba" and even palindromes such as "aa" exercise different interior base cases.

Common Mistakes and Interview Tips

Breaking the end loop after a non-palindromic prefix. In "aba", "ab" fails but the longer "aba" succeeds; skip that end and continue.
Reading pal[i + 1][j - 1] before computing it, or failing to short-circuit the length-one/two cases.
Saving the live path instead of a copy, so later pops corrupt already returned partitions.
Claiming O(n^2 times 2^n) for disjoint-piece scans: all pieces of one mask contain only n characters in total. Include output storage explicitly.

Key Takeaway

Partition searches pair well with precomputation: answer every repeated substring question once in a table, then let the walk spend its budget only on viable prefixes.