Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Return every way to cut the string so that every piece is a palindrome. The canonical answer is backtracking with a start index: from `start`, try every cut end; if `s[start..end]` is a palindrome, choose that prefix, recurse from `end + 1`, then un-choose. Record the path when `start` reaches the end of the string. Optionally precompute an `isPalindrome[i][j]` DP table so each palindrome check is O(1) instead of O(n).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you model the problem as choosing cut points (not elements), prune branches with a palindrome check, and correctly advance the recursion to `end + 1`. Bonus: precomputing the palindrome table with DP to make checks O(1) and quoting the right complexity.
Where candidates slip
Recursing from `start` or `end` instead of `end + 1` (overlapping or skipped characters), re-checking palindromes naively inside the hot loop (slower than needed), or forgetting to copy the path so all partitions corrupt.
How to stand out
State the cut-point model and the choose/explore/un-choose template, prune with the palindrome check, then offer the isPalindrome[i][j] DP precomputation, explaining how it drops each check to O(1) and giving the O(n · 2ⁿ) bound.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachExplore the full treeCollapse the tree
How to read it:Each node is a position `start`; each edge picks a palindromic prefix and jumps to the character after it. Branches whose prefix isn't a palindrome are pruned (red). Reaching the end of the string is a winning leaf (green).
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 1 · Optimal
Backtracking over Cut Points (Optimal)
1Hint 1Explore hintHide hint
Think of inserting cut bars between characters. From the current position, what are your choices for where the NEXT piece ends?
2Hint 2Explore hintHide hint
From `start`, let `end` range over every position ≥ start. The prefix `s[start..end]` is a candidate piece — but you only want to recurse into it when it's a palindrome.
3Hint 3Explore hintHide hint
Choose the palindromic prefix (append the substring), explore the remainder by recursing from `end + 1`, then un-choose (pop). When `start` reaches the end of the string, record a copy of the path.
A · Core idea
Model the problem as choosing where to cut. At each recursion level we sit at position start and decide where the next piece ends: let end sweep from start to the end of the string. For each end, the candidate piece is s[start..end]. We only descend into a cut when that piece is a palindrome — otherwise the branch can never yield a valid partition, so we skip it. We choose the piece (append the substring), explore the rest of the string by recursing from end + 1, then un-choose (pop). When start == len(s), every character has been swallowed by some palindromic piece, so the current path is a complete valid partition and we record a copy.
Why we branch on cut points, not on elements. Subsets and permutations choose which elements to include; here the elements (characters) are all used and in fixed order — the only freedom is where the boundaries fall. So the branching factor at position start is 'how long is the next piece', i.e. the choice of end. That reframing is the whole modelling insight: a partition problem is a 'choose the next boundary' backtracking problem.
Why the palindrome check is the prune. Without it we'd enumerate all 2^(n−1) ways to cut and filter at the end — but a cut that makes a non-palindromic prefix can never be completed into a valid answer, so we reject it immediately and never explore its subtree. This is classic backtracking pruning: test the constraint as early as possible (right at the cut) so dead branches die instantly. For "aab", the prefix "ab" fails the test, so the entire subtree under 'first piece = ab' is skipped.
Why we recurse from `end + 1` (not `start`, not `end`). Each character must belong to exactly one piece. After committing s[start..end] as a piece, the next piece must begin at the very next character, end + 1. Recursing from start would re-cut characters we already placed (overlap); recursing from end would re-use s[end] in two pieces. The +1 is what makes the pieces a clean partition that tiles the string.
Why record at `start == len(s)` and copy the path. Reaching the end means the cuts we made consumed the whole string with palindromic pieces — a complete answer. We snapshot path[:] because path is shared and mutated by the pops as we backtrack; appending the live list would leave every stored partition pointing at the same, later-emptied list. The always-valid all-singletons partition falls out naturally because every single character passes the palindrome test.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
s = "aab"Interactive diagram
Choose / explore / un-choose on "aab"
start=0Each downward edge commits a palindromic piece and advances start past it. The "ab" and "aab" prefixes fail the palindrome test, so those branches are pruned.
[["a","a","b"],["aa","b"]]C · Code with teaching comments
D · Why it works and complexityO(n · 2ⁿ) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
The choose/explore/un-choose skeleton here is byte-for-byte the same as Subsets — what changes is the branching (cut positions instead of element indices) and the prune (palindrome test instead of 'always allowed'). Recognising that 'partition a sequence under a per-piece predicate' maps onto the same template lets you reuse one mental model for Palindrome Partitioning, Word Break II, and Restore IP Addresses.
ComplexityO(n · 2ⁿ) time, O(n) space — There are up to 2^(n−1) ways to place cut bars, so up to O(2ⁿ) partitions in the worst case (e.g. "aaaa…"). Building/copying each partition costs O(n). With an O(1) palindrome check the total is O(n · 2ⁿ). Extra space beyond the output is the recursion depth and the path, both O(n) (plus O(n²) if you precompute the palindrome table).
E · Edge cases and pitfalls6s = "a" — end=0: "a" is a palindrome → recurse from 1 == len → record ["a"]. Returns [["a"]].Explore edge casesHide edge cases
Edge cases handled
s = "a"end=0: "a" is a palindrome → recurse from 1 == len → record ["a"]. Returns [["a"]].s = "aaa"Every substring of equal characters is a palindrome, so all 2² = 4 partitions are produced: [a,a,a], [a,aa], [aa,a], [aaa]. Worst-case branching.
Pitfalls
- Recursing from `start` or `end` instead of `end + 1` — causes overlapping pieces or a re-used character.
- Using exclusive/inclusive end indices inconsistently — `substring(start, end+1)` / `s[start:end+1]` must include s[end].
- Checking the palindrome only at the end instead of pruning per cut — explores dead subtrees needlessly.
- Appending the live `path` instead of a copy — every stored partition mutates to the same list.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic List<List<String>> partition(String s) { List<List<String>> results = new ArrayList<>(); backtrack(s, 0, new ArrayList<>(), results); return results; }Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Recursing from the wrong index
After taking the piece s[start..end], the next piece must begin at end+1. Recursing from `end` reuses s[end] in two pieces; recursing from `start` re-cuts already-placed characters.
Explore the code comparisonHide the code comparison
Recursing from the wrong index
After taking the piece s[start..end], the next piece must begin at end+1. Recursing from `end` reuses s[end] in two pieces; recursing from `start` re-cuts already-placed characters.
Don't write this
if is_palindrome(start, end):
path.append(s[start:end + 1])
backtrack(end, path) # reuses s[end] — overlap!
path.pop()Write this instead
if is_palindrome(start, end):
path.append(s[start:end + 1])
backtrack(end + 1, path) # next piece starts after this one
path.pop()2Generate-all-then-filter instead of pruning
Enumerating every cut and only checking palindromes at the leaf explores huge dead subtrees. Pruning at each cut (only descend when the prefix is a palindrome) kills those subtrees instantly.
Explore the code comparisonHide the code comparison
Generate-all-then-filter instead of pruning
Enumerating every cut and only checking palindromes at the leaf explores huge dead subtrees. Pruning at each cut (only descend when the prefix is a palindrome) kills those subtrees instantly.
Don't write this
for end in range(start, len(s)):
path.append(s[start:end + 1]) # take ANY prefix
backtrack(end + 1, path) # check palindromes only at the leaf
path.pop()Write this instead
for end in range(start, len(s)):
if is_palindrome(start, end): # prune here
path.append(s[start:end + 1])
backtrack(end + 1, path)
path.pop()3Storing the live path reference
`results.append(path)` stores the same list object; the pops on backtrack mutate it so every partition becomes identical. Snapshot with `path[:]`.
Explore the code comparisonHide the code comparison
Storing the live path reference
`results.append(path)` stores the same list object; the pops on backtrack mutate it so every partition becomes identical. Snapshot with `path[:]`.
Don't write this
if start == len(s):
results.append(path) # reference to a mutating list
returnWrite this instead
if start == len(s):
results.append(path[:]) # snapshot copy
returnRevise
Carry the pattern into the interview
Pattern to remember
Backtracking over cut points + palindrome check (choose → explore → un-choose)
Code pattern to memorize
def backtrack(start, path):
if start == len(s): results.append(path[:]); return
for end in range(start, len(s)):
if is_palindrome(start, end): # only cut where the prefix is a palindrome
path.append(s[start:end+1]) # choose this palindromic prefix
backtrack(end + 1, path) # explore the remainder
path.pop() # un-chooseRules to remember
- 1Branch on the cut point: from
start, everyend ≥ startis a candidate prefixs[start..end]. - 2Only recurse when the prefix is a palindrome — that's the pruning that keeps the tree small and the answers valid.
- 3Recurse from
end + 1(the character after the cut), never fromstart— each character belongs to exactly one piece. - 4Record when
start == len(s)— reaching the end means every character has been consumed by some palindromic piece. - 5Append a copy
path[:]of the list of substrings — the live path is mutated on backtrack. - 6Precompute
isPalindrome[i][j]with DP (or expand-around-center) to turn each check from O(n) into O(1) — a strong optimisation to mention.
Use this pattern when
- Asked for **all** ways to split a string under a per-piece predicate (here: palindrome)
- Each character must land in exactly one contiguous piece
- The predicate (palindrome) can be checked on a substring quickly
- You need the partitions themselves, not just a count or a minimum
Choose another pattern when
- Only the **minimum number of cuts** is needed → Palindrome Partitioning II, pure DP (don't enumerate)
- Only the **count** of valid partitions → DP over indices, not backtracking
- Pieces can overlap or be reordered → it's not a contiguous partition problem
- String is huge → exponential partitions make full enumeration intractable
Interview takeaway
Palindrome Partitioning is the 'partition a sequence' member of the backtracking family: instead of choosing elements, you choose cut points, and a predicate (palindrome) prunes invalid cuts. The choose/explore/un-choose skeleton is identical to Subsets — only the branching (cut positions) and the prune (palindrome check) change. Adding an isPalindrome DP table is the canonical hybrid that earns it the dynamic-programming tag.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical Backtracking over cut points with a per-piece predicate (choose → explore → un-choose). Recognise it whenever you must enumerate ALL ways to split a sequence so each contiguous piece satisfies a test. The skeleton matches Subsets; the predicate prune and `end + 1` advance are the partition-specific pieces. Precomputing an isPalindrome[i][j] DP table (the dynamic-programming half) makes each check O(1).
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Palindrome Partitioning IIComing soonOnly the MINIMUM number of cuts is needed → pure DP: dp[i] = min cuts for s[0..i], using an isPalindrome[i][j] table. Don't enumerate partitions.
- Word Break IIComing soonSame cut-point backtracking, but the per-piece predicate is 'is in the dictionary' instead of 'is a palindrome'; memoise by start index to avoid recomputation.
- Restore IP AddressesComing soonPartition into exactly 4 pieces, each a valid 0–255 octet → cut-point backtracking with a piece-count check and a per-octet validity prune.
- SubsetsSame choose/explore/un-choose skeleton — Subsets branches on element indices with no predicate; this branches on cut points with a palindrome predicate.