The choices here are not elements — they are cut positions.
Think of this like having a long chocolate bar made of several connected squares, and a knife. You can place your knife at any of the joints between the squares and make a cut. When you make a cut, you examine the piece you just broke off. If it's a valid palindrome, you put it in your pile and look at the remaining bar, deciding where to cut next. If the piece isn't a palindrome, you magically undo that cut and try cutting further down the bar instead.
Standing at index start, the piece you take next can end anywhere from start to the end of the string. Each ending is one branch. Take the piece only if it is a palindrome, recurse from just after it, then undo.
"aab", starting at 0: take "a" → recurse from 1 take "a" → recurse from 2 take "b" → recurse from 3 = end → record ["a","a","b"] ✓ take "ab" → not a palindrome, rejected take "aa" → recurse from 2 take "b" → end → record ["aa","b"] ✓ take "aab" → not a palindrome, rejected
This is the same start-index loop as 4.18.1 Subsets. Only the meaning of the loop variable changed: it is a cut point rather than an item index.
Recognising that is the point of the problem. When you can phrase the choices as "what do I take next, and where does it end", the template is unchanged.
class Solution: def partition(self, s: str) -> List[List[str]]: result = [] # (1) path = [] def is_palindrome(lo: int, hi: int) -> bool: # (2) while lo < hi: if s[lo] != s[hi]: return False lo += 1 hi -= 1 return True def backtrack(start: int): # (3) if start == len(s): # (4) consumed the whole string result.append(path[:]) return for end in range(start, len(s)): # (5) the piece is s[start..end] if not is_palindrome(start, end): # (6) continue # prune: not a valid piece path.append(s[start:end + 1]) # (7) backtrack(end + 1) # (8) continue after this piece path.pop() # (9) backtrack(0) return result
ts
function partition(s: string): string[][] { const result: string[][] = []; // (1) const path: string[] = []; function isPal(lo: number, hi: number): boolean { // (2) while (lo < hi) { if (s[lo] !== s[hi]) return false; lo++; hi--; } return true; } function backtrack(start: number): void { // (3) if (start === s.length) { // (4) result.push([...path]); return; } for (let end = start; end < s.length; end++) { // (5) if (!isPal(start, end)) continue; // (6) path.push(s.slice(start, end + 1)); // (7) backtrack(end + 1); // (8) path.pop(); // (9) } } backtrack(0); return result;}
(1) result collects every way of cutting the string, and path holds the pieces chosen so far.
(2) Is s[lo..hi] a palindrome? Two pointers move inward from both ends, as in 4.5.1. It works on positions, so no new string is created.
(3) backtrack(start) cuts the rest of the string, from position start onward.
(4) The whole string has been cut into pieces. Save a copy of path.
(5) Try every possible next piece: from start to end, for each end.
(6) Only palindromes are allowed as pieces. This check runs before going deeper, so a bad piece ends that branch at once.
(7) Take the piece,
(8) cut the rest of the string, starting right after this piece, and
(9) undo, ready to try a longer piece.
The palindrome check is the pruning, and it happens before recursing. That is what stops the search exploring every one of the 2^{n-1} possible cuttings — most branches die at the check.
is_palindrome takes indices, not a substring. Passing s[start:end+1] would allocate a new string on every check, which is O(n) of pure waste per call. Comparing in place with two pointers is the same discipline as 4.2 and 4.5.1.
backtrack(end + 1) — the next piece starts immediately after the one just taken.
The base case is start == len(s), meaning the whole string has been consumed. There is no leftover to worry about, because every branch takes a piece and moves past it.
The palindrome check costs O(n) and is called from every node of the tree, and many of those checks repeat. You can compute all of them once, in O(n^2), with a small dynamic program:
python
n = len(s)pal = [[False] * n for _ in range(n)]for hi in range(n): for lo in range(hi, -1, -1): if s[lo] == s[hi] and (hi - lo < 2 or pal[lo + 1][hi - 1]): pal[lo][hi] = True
Read the condition: s[lo..hi] is a palindrome when its two ends match and the inside is already known to be one. hi - lo < 2 covers the pieces of length 1 and 2, which have no inside.
The loop order matters — lo counts downwards so that pal[lo+1][hi-1] is already filled when it is needed. That "fill the table in an order where the dependencies already exist" idea is the core of 4.24.
With the table, is_palindrome(lo, hi) becomes an O(1) lookup and the whole search drops a factor of n. Say this even if you do not write it — recognising the repeated work is the observation being tested.
O(2^{n-1} \times n) in the worst case. A string of n characters has n−1 gaps and each is either cut or not, so there are 2^{n-1} possible partitions; copying each result costs O(n).
The worst case is a string like "aaaa", where every piece is a palindrome and nothing is ever pruned. On ordinary strings the pruning removes almost everything.
O(n) space for the recursion, or O(n^2) with the precomputed table.
Let's break this down:
Time Complexity: There are n-1 possible cut points in a string of length n. For each cut point, we either make a cut or we don't, giving 2^{n-1} possible partitions. For each valid partition, we slice and copy strings, taking O(n) time. The palindrome check itself takes O(n) string traversal, giving O(n \cdot 2^{n-1}) total worst-case time (like the string "aaaaa"). The DP precomputation reduces the inner check to O(1), but the copying still binds the overall worst case to O(n \cdot 2^{n-1}).
Space Complexity: The maximum depth of the recursion tree is n (if we cut every single character). The path array stores at most n items. If we use the DP table, it takes O(n^2) space. So O(n) or O(n^2) depending on the approach.
Palindrome Partitioning II — the minimum number of cuts. Enumerating every partition and taking the smallest is far too slow. Because you only need an optimum rather than every answer, it becomes DP: O(n^2). 4.23.
Word Break II — cut a string into dictionary words and return all of them. Identical template with the dictionary check replacing the palindrome check.
Restore IP Addresses — cut a digit string into four valid octets. Same template, with a validity check and a piece-count limit.
The recurring dividing line:all the answers means backtracking; the best answer or how many means DP. Combination Sum II and Combination Sum IV sit on either side of it, and so do these two Palindrome Partitioning problems.
"What are the choices at each step?" Where the next piece ends.
"Where is the pruning?" The palindrome check before recursing.
"Why pass indices instead of substrings to the checker?" Slicing allocates and costs O(n) per check.
"Can you avoid re-checking the same substrings?" Precompute an n \times n table in O(n^2).
"What if you only needed the minimum number of cuts?" DP, not backtracking, and say why: you want one optimum, not every arrangement.
One thing to volunteer: point out that this is the subsets template where the loop variable is a cut position. Naming the reused skeleton is worth more than the code.