Palindrome Partitioning: Backtracking + DP Pre-check Pattern

Problem Statement#

You are given a string s. Partition it such that every substring of the partition is a palindrome. Return all possible palindrome partitionings of s.

Example: for s = "aab", the answer is [["a","a","b"], ["aa","b"]]. The catch is the word "all" — interviewers love this problem because it sits at the exact intersection of backtracking and string DP, two of the most-tested topics in FAANG interviews.

Why This Problem Matters#

Palindrome Partitioning (LeetCode 131) is a recurring favorite at Meta, Amazon, Google, and Microsoft phone screens because it tests three skills in one shot: building a clean backtracking template, recognizing where DP can speed up a recursive subroutine, and managing recursion-tree state without bugs. Companies use it to filter candidates who can write recursion that does not blow up on edge cases like empty strings, single characters, or all-identical strings such as "aaaa".

If you can explain the decision tree, justify the complexity, and add the palindrome DP precomputation under pressure, you signal that you have internalized backtracking as a pattern, not memorized one solution. That is exactly what bar raisers look for.

The Core Insight (decision tree / state space)#

At every index start, we ask one question: "Where does the next palindrome end?" If s[start..end] is a palindrome, we commit it as the next chunk and recurse on start = end + 1. If it is not, we prune that branch immediately.

This gives us a decision tree where each node represents a starting index, and the children are all valid palindrome cuts beginning at that index. The leaves are reached when start == n, meaning the whole string has been consumed by palindromes — a complete combination.

Two key observations make this efficient:

1. The number of palindrome partitionings is bounded by the Catalan-like count, but in practice palindromes are sparse, so pruning is aggressive.
2. We will check the same substring s[i..j] for palindromicity many times across different recursion branches. Precomputing is_pal[i][j] once in O(n^2) time turns each check into O(1), eliminating duplicated work without changing the shape of the decision tree.

Visual Dry Run (recursion tree)#

For s = "aab":

                 partition("aab", start=0)
                /            |             \
         "a"|"ab"      "aa"|"b"        "aab" (not pal, pruned)
            |              |
       partition(1)    partition(2)
        /     \              \
   "a"|"b"  "ab"(skip)    "b"
       |                     |
  partition(2)          partition(3) -> LEAF: ["aa","b"]
       |
     "b"
       |
  partition(3) -> LEAF: ["a","a","b"]

Notice how "ab" is checked but rejected — that is the palindrome guard pruning the branch. The DP table makes that rejection O(1).

Solution (Optimal) — Python + JavaScript with backtracking template, complexity#

The template is the classic backtracking shape: choose, recurse, un-choose. The palindrome DP is built bottom-up so that is_pal[i][j] depends on is_pal[i+1][j-1], which is already computed.

def partition(s):
    n = len(s)
    is_pal = [[False] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            is_pal[i][j] = (s[i] == s[j]) and (j - i <= 2 or is_pal[i + 1][j - 1])
 
    result, current = [], []
 
    def backtrack(start):
        if start == n:
            result.append(current[:])
            return
        for end in range(start, n):
            if is_pal[start][end]:
                current.append(s[start:end + 1])
                backtrack(end + 1)
                current.pop()
 
    backtrack(0)
    return result

function partition(s) {
  const n = s.length;
  const isPal = Array.from({ length: n }, () => Array(n).fill(false));
  for (let i = n - 1; i >= 0; i--) {
    for (let j = i; j < n; j++) {
      isPal[i][j] = s[i] === s[j] && (j - i <= 2 || isPal[i + 1][j - 1]);
    }
  }
  const result = [];
  const current = [];
  const backtrack = (start) => {
    if (start === n) {
      result.push([...current]);
      return;
    }
    for (let end = start; end < n; end++) {
      if (isPal[start][end]) {
        current.push(s.slice(start, end + 1));
        backtrack(end + 1);
        current.pop();
      }
    }
  };
  backtrack(0);
  return result;
}

Complexity: time is O(n times 2^n) in the worst case (a string like "aaaa..." has 2^(n-1) partitions, and copying each one costs O(n)). Space is O(n^2) for the DP table plus O(n) for recursion depth.

Common Mistakes#

• Recomputing palindrome checks inside the recursion without memoization. This turns a fast solution into a TLE on long inputs.
• Forgetting to copy current when appending to result. Pushing the reference means every entry mutates as you backtrack.
• Off-by-one on the slice. Use s[start:end+1] in Python and s.slice(start, end + 1) in JavaScript so the substring is inclusive of end.
• Building the DP table top-down and accessing is_pal[i+1][j-1] before it is filled.

Interview Tips#

• Start by stating both the brute-force and the optimized approach. Saying "I will check palindromes in O(1) using a precomputed table" earns immediate credit.
• Draw the recursion tree on the whiteboard for "aab" first — interviewers reward visual thinkers.
• Mention LeetCode 132 (Min Cuts) and LeetCode 1278 (Palindrome Partitioning III) as natural follow-ups; this shows you see the family.

Follow-up Questions#

• Minimum cuts to partition into palindromes (LeetCode 132).
• Partition into exactly k palindromic parts with minimum changes (LeetCode 1278).
• Count the number of palindrome partitionings without enumerating them — pure DP, O(n^2).
• What if the alphabet is huge? The DP table dominates and stays O(n^2) regardless.

Key Takeaways#

• Palindrome Partitioning is the textbook example of combining backtracking with a precomputed DP table.
• The decision tree branches on "where does the next palindrome end" — a clean state-space formulation.
• Always precompute is_pal[i][j] before recursing; it is the single most impactful optimization.
• Worst case is exponential because the answer itself is exponential — you cannot beat that.
• The same template generalizes to Word Break II, Restore IP Addresses, and Expression Add Operators.
• Mastering this problem unlocks half of the recursion-and-backtracking interview canon.

Sources:

• Palindrome Partitioning - LeetCode
• 131. Palindrome Partitioning - In-Depth Explanation