Palindrome Partitioning

How it works

This approach combines Dynamic Programming and pure recursion (return-based).

• We first precompute all palindromic substrings using DP.
• Then we use recursion where each recursive call:
  • returns all valid palindrome partitions starting from a given index.
• Instead of maintaining a global result or path, each recursive call builds and returns its own list of partitions, which makes the logic clean and declarative.

Think of it as:

“All partitions starting at index i =
choose a palindrome s[i..j] + all partitions starting at j + 1”

Steps

Step 1: Precompute Palindromes (DP)

1. Create a 2D table dp[i][j].
2. dp[i][j] = True if substring s[i..j] is a palindrome.
3. Fill the table by increasing substring length:
   • Characters at ends must match.
   • Inner substring must already be a palindrome (or be empty).

---

Step 2: Recursive Construction

1. Define dfs(i):
   • Returns all palindrome partitions starting from index i.
2. Base case:
   • If i == len(s), return [[]] (one empty partition).
3. Recursive case:
   • For every j from i to end:
     • If dp[i][j] is true:
       • Recursively get partitions from dfs(j + 1).
       • Prepend s[i..j] to each returned partition.
4. Return the collected partitions.

Complexity

• Time complexity: O(n * 2 ^ n)
• Space complexity:
  • O(n ^ 2) extra space.
  • O(n * 2 ^ n) space for the output list.

Things to watch for

Forgetting to Copy the Partition Before Adding to Results

When adding the current partition to the results list, you must add a copy of the list, not a reference to it. Since backtracking modifies the same partition list, adding the reference directly means all entries in the result will point to the same (eventually empty) list.

Incorrect Base Case in Backtracking

The base case should trigger when the starting index reaches the end of the string, indicating a complete valid partition. A common mistake is to check i > len(s) instead of i >= len(s) or i == len(s), causing missed partitions or index errors.

Redundant Palindrome Checks Without Memoization

Repeatedly checking whether the same substring is a palindrome across different recursion branches wastes time. Without precomputing palindrome information using DP, the same substring may be checked O(2^n) times, significantly slowing down the solution for longer strings.

from typing import List

class Solution:

    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        for l in range(1, n + 1):
            for i in range(n - l + 1):
                dp[i][i + l - 1] = (s[i] == s[i + l - 1] and
                                    (i + 1 > (i + l - 2) or
                                    dp[i + 1][i + l - 2]))

        def dfs(i):
            if i >= n:
                return [[]]

            ret = []
            for j in range(i, n):
                if dp[i][j]:
                    nxt = dfs(j + 1)
                    for part in nxt:
                        cur = [s[i : j + 1]] + part
                        ret.append(cur)
            return ret

        return dfs(0)

class Solution {
public:
    vector<vector<string>> partition(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        for (int l = 1; l <= n; l++) {
            for (int i = 0; i <= n - l; i++) {
                dp[i][i + l - 1] = (s[i] == s[i + l - 1] &&
                                    (i + 1 > (i + l - 2) ||
                                    dp[i + 1][i + l - 2]));
            }
        }

        return dfs(s, dp, 0);
    }

    vector<vector<string>> dfs(string& s, vector<vector<bool>>& dp, int i) {
        if (i >= s.size()) {
            return {{}};
        }

        vector<vector<string>> ret;
        for (int j = i; j < s.size(); j++) {
            if (dp[i][j]) {
                auto nxt = dfs(s, dp, j + 1);
                for (auto& part : nxt) {
                    vector<string> cur;
                    cur.push_back(s.substr(i, j - i + 1));
                    cur.insert(cur.end(), part.begin(), part.end());
                    ret.push_back(cur);
                }
            }
        }
        return ret;
    }
};