Palindrome Partitioning: cutting a string until every piece reads the same forwards and backwards

The constraint is 1 <= s.length <= 16. That number — sixteen — is the whole story. Sixteen characters means at most fifteen cut points, and at most 2^15 = 32768 subsets of those positions. Even the brute-force approach that checks every partition and re-evaluates palindromes inline will finish fast. The constraint is not telling you to use backtracking; it is handing you permission to enumerate everything. What you decide to precompute is purely a trade-off in constant factors, not a correctness question.

The output shape is "all possible partitions where every piece is a palindrome." The two examples make the structure clear: for "aab", the answers are ["a","a","b"] and ["aa","b"]. For "a", only ["a"] is possible — a single character is always a palindrome.

The problem

Given a string s, partition it such that every substring in the partition is a palindrome, and return all possible palindrome partitions. Full statement: LeetCode 131.

Constraints:
- 1 <= s.length <= 16
- s contains only lowercase English letters.

What the constraints tell you about the design space

s.length <= 16 and lowercase English only. Both constraints do real work.

n <= 16 rules out any concern about exponential blowup in practice. In the worst case, the input is all identical characters ("aaaa...a"), where every prefix is a palindrome and the recursion branches at every step. The maximum output size in that case is the number of compositions of n, which is 2^(n-1). For n = 16, that is 32768 partitions. Fast.

Lowercase English only means you have at most 26 distinct characters. It simplifies palindrome checking (no case normalization needed) and makes DP initialization trivial. You never need to worry about Unicode, case sensitivity, or special characters.

No constraint says "find the minimum number of cuts" — that is LeetCode 132, a harder problem. Here you enumerate, not optimize.

Approach 1: Backtracking with inline palindrome check

The recursion is straightforward: start at position start, try every prefix ending at position end, check if s[start:end] is a palindrome, and if so, add it to the current path and recurse from end. When start reaches the length of the string, record the completed partition.

class Solution:
    def partition(self, s: str) -> list[list[str]]:
        def is_palindrome(t: str) -> bool:
            return t == t[::-1]
 
        def backtrack(start: int, path: list[str]) -> None:
            if start == len(s):
                result.append(path[:])
                return
            for end in range(start + 1, len(s) + 1):
                sub = s[start:end]
                if is_palindrome(sub):
                    path.append(sub)
                    backtrack(end, path)
                    path.pop()
 
        result: list[list[str]] = []
        backtrack(0, [])
        return result

public class Solution {
    public IList<IList<string>> Partition(string s) {
        var result = new List<IList<string>>();
 
        bool IsPalindrome(string t) {
            int l = 0, r = t.Length - 1;
            while (l < r) {
                if (t[l] != t[r]) return false;
                l++; r--;
            }
            return true;
        }
 
        void Backtrack(int start, List<string> path) {
            if (start == s.Length) {
                result.Add(new List<string>(path));
                return;
            }
            for (int end = start + 1; end <= s.Length; end++) {
                string sub = s.Substring(start, end - start);
                if (IsPalindrome(sub)) {
                    path.Add(sub);
                    Backtrack(end, path);
                    path.RemoveAt(path.Count - 1);
                }
            }
        }
 
        Backtrack(0, new List<string>());
        return result;
    }
}

The C# IsPalindrome uses two pointers rather than a reverse-and-compare because C# does not have a built-in string reverse that is as concise as Python's [::-1]. Both are O(k) for a substring of length k.

Hand trace through "aab"

Step by step:

• start=0. Try "a" (palindrome) -> path = ["a"], recurse with start=1.
  • start=1. Try "a" (palindrome) -> path = ["a","a"], recurse with start=2.
    • start=2. Try "b" (palindrome) -> path = ["a","a","b"], recurse with start=3.
      • start=3 == len(s) -> record ["a","a","b"].
    • Pop "b".
  • Pop "a". Try "ab" -> not a palindrome, skip.
  • No more branches.
• Pop first "a". Try "aa" (palindrome) -> path = ["aa"], recurse with start=2.
  • start=2. Try "b" (palindrome) -> path = ["aa","b"], recurse with start=3.
    • start=3 == len(s) -> record ["aa","b"].
  • Pop "b".
• Pop "aa". Try "aab" -> not a palindrome, skip.
• Done. Result: [["a","a","b"], ["aa","b"]].

Complexity for Approach 1

Time: O(n * 2^n). The backtracking explores O(2^n) partitions in the worst case (all-same input). For each partition, the path[:] copy at the leaf costs O(n). The inline palindrome checks add another O(n) per candidate prefix across each level. The dominant term is O(n * 2^n).

Space: O(n) auxiliary — the recursion depth is at most n (each level consumes at least one character), and path holds at most n entries. The result list itself grows to O(2^n * n) in the worst case, but that is output space, not working space.

Approach 2: DP precomputation, then backtracking

The inefficiency in Approach 1 is that the same substring — say s[0:3] — may be checked for palindromes multiple times across different recursive branches. The fix is to compute all palindrome statuses upfront in a 2D boolean table, so that every call to isPalindrome(s[i..j]) during the search becomes an O(1) table lookup.

The DP recurrence is the standard one: dp[i][j] is true if s[i] == s[j] and dp[i+1][j-1] is true. Base cases: every single character dp[i][i] = true; pairs dp[i][i+1] = (s[i] == s[i+1]). Fill by increasing length.

class Solution:
    def partition(self, s: str) -> list[list[str]]:
        n = len(s)
 
        # Build palindrome table
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = True
        for i in range(n - 1):
            dp[i][i + 1] = s[i] == s[i + 1]
        for length in range(3, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                dp[i][j] = s[i] == s[j] and dp[i + 1][j - 1]
 
        def backtrack(start: int, path: list[str]) -> None:
            if start == n:
                result.append(path[:])
                return
            for end in range(start, n):
                if dp[start][end]:
                    path.append(s[start : end + 1])
                    backtrack(end + 1, path)
                    path.pop()
 
        result: list[list[str]] = []
        backtrack(0, [])
        return result

public class Solution {
    public IList<IList<string>> Partition(string s) {
        int n = s.Length;
        var result = new List<IList<string>>();
 
        // Build palindrome table
        bool[,] dp = new bool[n, n];
        for (int i = 0; i < n; i++) dp[i, i] = true;
        for (int i = 0; i < n - 1; i++) dp[i, i + 1] = s[i] == s[i + 1];
        for (int len = 3; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                dp[i, j] = s[i] == s[j] && dp[i + 1, j - 1];
            }
        }
 
        void Backtrack(int start, List<string> path) {
            if (start == n) {
                result.Add(new List<string>(path));
                return;
            }
            for (int end = start; end < n; end++) {
                if (dp[start, end]) {
                    path.Add(s.Substring(start, end - start + 1));
                    Backtrack(end + 1, path);
                    path.RemoveAt(path.Count - 1);
                }
            }
        }
 
        Backtrack(0, new List<string>());
        return result;
    }
}

Notice the index shift: in Approach 1 the inner loop runs for end in range(start + 1, len(s) + 1) and slices s[start:end]. In Approach 2 the loop runs for end in range(start, n) and indexes dp[start][end], then slices s[start:end+1]. Both cover the same substrings; Approach 2 uses inclusive end indices because that is the natural representation for the DP table (dp[i][j] covering s[i..j] inclusive).

How the DP table fills for "aab"

Indices:  0='a'  1='a'  2='b'

Length 1 (base):
  dp[0][0] = True   ("a")
  dp[1][1] = True   ("a")
  dp[2][2] = True   ("b")

Length 2:
  dp[0][1] = (s[0]==s[1]) = ('a'=='a') = True    ("aa")
  dp[1][2] = (s[1]==s[2]) = ('a'=='b') = False   ("ab")

Length 3:
  dp[0][2] = (s[0]==s[2]) and dp[1][1]
           = ('a'=='b') and True
           = False                                  ("aab")

Final table (dp[i][j], row=i, col=j):
       j=0    j=1    j=2
i=0    T      T      F
i=1           T      F
i=2                  T

Now the backtracking reads dp[0][0]=T (take "a"), dp[0][1]=T (take "aa"), dp[0][2]=F (skip "aab"). At start=1 it reads dp[1][1]=T (take "a"), dp[1][2]=F (skip "ab"). The recursion never re-evaluates a palindrome — every lookup is array indexing.

Complexity for Approach 2

Time: O(n^2 + n * 2^n). The DP fill is O(n^2) — there are n^2 / 2 table entries and each fills in O(1). The backtracking is still O(n * 2^n) in the worst case for the same reason as before: the number of valid partitions and the copy cost at leaves. For n = 16, n^2 = 256 is completely dominated by the backtracking term.

Space: O(n^2) for the DP table plus O(n) for the call stack and path. The table is an n x n boolean grid.

Edge cases that matter

Single character (s = "a"): in both approaches, start=0, end=0 (or end=1 in Approach 1), the single character is a palindrome, start reaches 1 which equals len(s), and ["a"] is recorded. One result, correctly.

All identical characters (s = "aaaa"): every substring is a palindrome. The backtracking explodes to 2^(n-1) results (all compositions of n). For n = 16, that is 32768. Approach 1 re-evaluates palindromes many times (every prefix of "aaaa..." is checked repeatedly across different branches); Approach 2 checks each dp[i][j] once. The constant-factor difference is most visible here.

No palindromes longer than 1 (s = "abcd"): every cut in the output is a single character. The backtracking produces exactly one result: ["a","b","c","d"]. Both approaches handle this trivially — the pruning never eliminates a branch early because no cross-character palindromes exist, but the recursion depth is n and there is only one leaf.

String where the whole input is a palindrome (s = "aba"): dp[0][2] = True. The backtracking now has an extra branch at start=0 where the entire string is taken as one piece. The results include ["aba"] alongside ["a","b","a"]. No special handling needed; the DP table captures it.

Length 2 (s = "aa"): dp[0][1] = True. Results: ["a","a"] and ["aa"]. Two entries, both correct.

Comparison of both approaches

For n = 16, the difference in palindrome check cost is O(16) vs O(1) per lookup. The backtracking still drives the runtime. In practice the DP version is faster because it eliminates repeated computation, but both pass comfortably within n <= 16.

What I would actually ship, and why

I would use Approach 2 — the DP-precomputed version — in a production code review. The reason is not speed at this input size. It is clarity of separation: the palindrome oracle is computed once, separately, before the search begins. Anyone reading the backtracking loop does not need to think about how palindromes are checked — the table is there, the lookup is a boolean indexing operation. The code separates concerns cleanly.

Approach 1 is the right starting point to explain the logic. It is shorter, has no setup phase, and makes the recursion structure obvious. In an interview whiteboard setting I might write Approach 1 first and then say "and we can optimize by precomputing palindromes into a 2D DP table to avoid redundant checks."

The one context where I'd prefer Approach 1 is if n were even smaller and the problem were embedded in a larger system where the extra O(n^2) allocation for the DP table has a cost I care about. At n = 16, that is at most 256 booleans — negligible. But the principle is real: preprocessing has an upfront cost, and for small enough inputs the naive check is fine.

The underlying pattern: choose-explore-unchoose

Both approaches use the same recursion skeleton that runs through this entire backtracking series: at each step, choose a candidate (a palindromic prefix), explore the subproblem from the new position, then unchoose (pop from the path). The termination condition is reaching the end of the string.

What makes Palindrome Partitioning specific is the pruning rule: you only recurse if the current prefix is a palindrome. That is not a universal constraint like "each element can be used once" (Subsets) or "order matters" (Permutations) — it is a content-based filter on the candidate. The DP precomputation is just a way to make that filter cheap.

The transferable mental model: backtracking over a string is a recursion over cut points. You are choosing which position to cut next, and your validity check determines whether to pursue a branch. Any problem that says "enumerate all splits of a string satisfying property P" maps to this same structure — replace the palindrome check with whatever check P requires.

Where this fits in the backtracking series

This series has moved through Subsets, Subsets II, Combination Sum, Combination Sum II, Permutations, and Word Search. Palindrome Partitioning is problem seven and is the first in the series where the branching condition is a non-trivial string property rather than a set-membership rule. The decision tree has the same shape as Combination Sum — at each position you pick a piece and move forward — but what makes a piece valid is richer.

Palindrome Partitioning II (132) is the natural follow-on: instead of enumerating all partitions, find the minimum number of cuts to make every piece a palindrome. It drops the backtracking entirely and becomes a DP-only problem. The palindrome table you build in Approach 2 here is exactly what 132 also needs. If this problem is comfortable, 132 is the right next step.

Word Break (139) shares the same cut-point recursion but replaces "is this piece a palindrome" with "is this piece in the dictionary." It asks for a boolean answer (can the string be segmented?) rather than enumerating all ways, which makes it a 1D DP problem rather than backtracking.

Restore IP Addresses (93) is another "partition a string into pieces satisfying a constraint" problem — three dots placed in exactly three positions such that each segment is a valid IP octet. Smaller branching factor (at most 3 characters per segment), but the skeleton is identical.

Letter Combinations of a Phone Number (17) has the same backtracking shape but works over a mapping (digit to letters) rather than a string split. It is structurally simpler, but the choose-explore-unchoose skeleton is the same.