Problem Description

Given a string s, you need to partition it into substrings where every substring in the partition is a palindrome. A palindrome is a string that reads the same forwards and backwards. Your task is to return all possible ways to partition the string such that each part is a palindrome.

For example, if s = "aab", the valid partitions would be:

• [["a","a","b"], ["aa","b"]]

The first partition breaks the string into three palindromes: "a", "a", and "b". The second partition breaks it into two palindromes: "aa" and "b".

The solution uses a two-step approach:

1. Preprocessing with Dynamic Programming: First, it builds a 2D table f[i][j] that stores whether the substring from index i to j is a palindrome. This is done by checking if the characters at positions i and j are equal and if the substring between them (from i+1 to j-1) is also a palindrome. The table is filled from bottom to top and left to right.

2. Depth-First Search with Backtracking: The dfs function explores all possible partitions starting from index i. For each position, it tries all possible ending positions j where the substring s[i:j+1] is a palindrome (checked using the preprocessed table). When a valid palindrome substring is found, it's added to the current partition t, and the search continues from position j+1. When the entire string is processed (i == n), the current partition is added to the answer. The backtracking step removes the last added substring to explore other possibilities.

The algorithm systematically explores all valid ways to partition the string into palindromes and returns all possible partitioning schemes.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• No: The problem involves partitioning a string into palindromic substrings, not nodes and edges as in graph problems.

Need to solve for kth smallest/largest?

• No: The problem asks for all possible palindrome partitions, not finding the kth smallest or largest element.

Involves Linked Lists?

• No: The problem works with strings and their partitions, not linked list data structures.

Does the problem have small constraints?

• Yes: String partitioning problems typically have manageable constraints since we need to explore all possible ways to partition the string. The exponential nature of generating all partitions means the input size is usually limited.

Brute force / Backtracking?

• Yes: We need to explore all possible ways to partition the string where each partition is a palindrome. This requires trying different partition points, checking if substrings are palindromes, and backtracking when a path doesn't work out. The backtracking approach systematically explores all valid partitioning schemes.

Conclusion: The flowchart correctly leads us to use a Backtracking approach. This aligns perfectly with the solution, which uses DFS with backtracking to explore all possible palindrome partitions. The algorithm tries each valid palindrome substring, adds it to the current partition, recursively processes the remaining string, and backtracks to explore other possibilities.

Intuition

When we need to find all possible ways to partition a string into palindromes, we're essentially making a series of decisions: "Where should I make the next cut in the string?" At each position, we have multiple choices - we can cut after one character, two characters, three characters, and so on, as long as the resulting substring is a palindrome.

This decision-making process naturally forms a tree structure. Starting from the beginning of the string, we explore all valid palindrome substrings that start from index 0. For each valid palindrome we find, we've made a partition decision, and now we need to recursively solve the same problem for the remaining part of the string.

The key insight is that we need to explore ALL possible valid partitions, not just find one. This means we can't be greedy - we must systematically try every possibility. When we choose a palindrome substring and move forward, we might later need to come back and try a different partition point. This "try, explore, and undo" pattern is the essence of backtracking.

To make this efficient, we can precompute which substrings are palindromes. Without this preprocessing, we'd be checking the same substring multiple times during our exploration. By building a 2D table f[i][j] that tells us whether substring from index i to j is a palindrome, we can instantly verify if a partition choice is valid during our backtracking process.

The backtracking works by maintaining a current partition list t. We add a palindrome substring to this list, recursively explore the rest of the string, and then remove (backtrack) the substring to try other possibilities. When we've successfully partitioned the entire string (reached the end), we've found one valid solution and add it to our answer collection.

Solution Approach

The solution implements the backtracking approach with preprocessing optimization as described in the reference approach.

Step 1: Preprocessing Palindrome Information

First, we build a 2D boolean table f[i][j] where f[i][j] = True if the substring s[i..j] is a palindrome. The table is filled using dynamic programming:

f = [[True] * n for _ in range(n)]
for i in range(n - 1, -1, -1):
    for j in range(i + 1, n):
        f[i][j] = s[i] == s[j] and f[i + 1][j - 1]

• We initialize all diagonal elements as True (single characters are palindromes)
• We iterate from bottom to top (i from n-1 to 0) and left to right (j from i+1 to n)
• A substring is a palindrome if its first and last characters match AND the substring between them is also a palindrome
• The condition f[i][j] = s[i] == s[j] and f[i + 1][j - 1] checks both conditions

Step 2: DFS with Backtracking

The dfs(i) function explores all valid partitions starting from index i:

def dfs(i: int):
    if i == n:
        ans.append(t[:])
        return
    for j in range(i, n):
        if f[i][j]:
            t.append(s[i : j + 1])
            dfs(j + 1)
            t.pop()

The algorithm works as follows:

1. Base Case: When i == n, we've successfully partitioned the entire string. We add a copy of the current partition t to our answer list.

2. Recursive Case: For the current position i, we try all possible ending positions j from i to n-1:

   • Check if s[i..j] is a palindrome using our preprocessed table f[i][j]
   • If it is, add this substring to our current partition t
   • Recursively process the remaining string starting from j + 1
   • Backtrack by removing the last added substring with t.pop()

Data Structures Used:

• f: 2D boolean array for palindrome lookup in O(1) time
• ans: List to store all valid partition combinations
• t: Temporary list to build current partition during DFS

The time complexity is O(n × 2^n) where n is the length of the string, as in the worst case we might have 2^n possible partitions and each takes O(n) to build. The space complexity is O(n^2) for the palindrome table plus O(n) for the recursion stack depth.

Example Walkthrough

Let's walk through the solution with s = "aab":

Step 1: Build the Palindrome Table

We create a 3×3 table f where f[i][j] indicates if substring from index i to j is a palindrome:

Initial table (all diagonals are True):
    0   1   2
0 [ T   ?   ? ]
1 [ -   T   ? ]
2 [ -   -   T ]

Now we fill the table from bottom-right to top-left:

• f[1][2]: Is "ab" a palindrome? s[1] == s[2] → 'a' ≠ 'b' → False
• f[0][1]: Is "aa" a palindrome? s[0] == s[1] → 'a' == 'a' → True
• f[0][2]: Is "aab" a palindrome? s[0] == s[2] → 'a' ≠ 'b' → False

Final table:
    0   1   2
0 [ T   T   F ]
1 [ -   T   F ]
2 [ -   -   T ]

Step 2: DFS with Backtracking

Starting with dfs(0), t = [], ans = []:

1. dfs(0): Try partitions starting at index 0

   • j = 0: f[0][0] = True (substring "a")
     • Add "a" to t: t = ["a"]
     • Call dfs(1)

2. dfs(1): Try partitions starting at index 1

   • j = 1: f[1][1] = True (substring "a")
     • Add "a" to t: t = ["a", "a"]
     • Call dfs(2)

3. dfs(2): Try partitions starting at index 2

   • j = 2: f[2][2] = True (substring "b")
     • Add "b" to t: t = ["a", "a", "b"]
     • Call dfs(3)

4. dfs(3): Base case i == 3

   • Add ["a", "a", "b"] to ans
   • Return

5. Back to dfs(2): Pop "b", no more j values, return

6. Back to dfs(1): Pop "a"

   • j = 2: f[1][2] = False (substring "ab" not palindrome)
   • No more j values, return

7. Back to dfs(0): Pop "a"

   • j = 1: f[0][1] = True (substring "aa")
     • Add "aa" to t: t = ["aa"]
     • Call dfs(2)

8. dfs(2): Try partitions starting at index 2

   • j = 2: f[2][2] = True (substring "b")
     • Add "b" to t: t = ["aa", "b"]
     • Call dfs(3)

9. dfs(3): Base case

   • Add ["aa", "b"] to ans
   • Return

10. Backtrack and complete remaining iterations

Final Result: ans = [["a", "a", "b"], ["aa", "b"]]

The algorithm systematically explores all valid palindrome partitions through DFS, using the precomputed table for O(1) palindrome checks, and backtracks to try alternative partition points.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × 2^n)

The algorithm uses backtracking to generate all possible palindrome partitions. The preprocessing step to build the palindrome table f takes O(n^2) time. For the backtracking part, in the worst case where every substring is a palindrome (like "aaaa"), we need to decide at each position whether to make a cut or not, leading to 2^(n-1) possible partitions. For each valid partition, we need O(n) time to construct the substring and add it to the result. Therefore, the overall time complexity is O(n × 2^n).

Space Complexity: O(n^2)

The space complexity consists of several components:

• The 2D table f for storing palindrome information requires O(n^2) space
• The recursion stack depth can go up to O(n) in the worst case
• The temporary list t stores at most n elements, requiring O(n) space
• The result list ans stores all partitions, but this is not counted as auxiliary space since it's part of the output

The dominant factor is the palindrome table f, making the overall space complexity O(n^2).

Common Pitfalls

1. Incorrect DP Table Initialization for Edge Cases

A common mistake is not properly handling the DP table initialization, particularly for substrings of length 1 and 2. While the provided solution initializes the entire table to True, which works because:

• Diagonal elements (single characters) should be True
• We only fill positions where j > i, so the initial True values for j <= i don't affect the result

However, developers often make errors when trying to optimize or modify this initialization:

Incorrect approach:

# Wrong: Forgetting that length-2 palindromes need special handling
is_palindrome = [[False] * n for _ in range(n)]
for i in range(n):
    is_palindrome[i][i] = True  # Only handling length-1

# This fails for adjacent equal characters like "aa"

Correct approach:

# The current solution handles this elegantly by:
# 1. Initializing everything to True
# 2. Only checking i+1 to j-1 when j > i, which naturally handles length-2 cases

2. Index Out of Bounds When Checking Inner Substring

Another pitfall occurs when checking is_palindrome[i + 1][j - 1] without ensuring it's valid:

Problem scenario: When j = i + 1 (substring of length 2), accessing is_palindrome[i + 1][j - 1] means accessing is_palindrome[i + 1][i], which is checking a "reverse" range.

Why the current solution works: The initialization of all values to True means is_palindrome[i + 1][i] is True, which is semantically correct (an empty substring between two matching characters forms a palindrome).

Alternative explicit solution:

for i in range(n - 1, -1, -1):
    for j in range(i + 1, n):
        if j - i == 1:  # Length 2 substring
            is_palindrome[i][j] = s[i] == s[j]
        else:  # Length > 2
            is_palindrome[i][j] = s[i] == s[j] and is_palindrome[i + 1][j - 1]

3. Creating Deep vs Shallow Copies

Common mistake:

# Wrong: This creates references, not copies
result.append(current_partition)  # All results will point to the same list!

Correct approach (as in the solution):

result.append(current_partition[:])  # Creates a new list copy

Without creating a copy, all entries in result would reference the same list object, which gets modified during backtracking, resulting in an empty or incorrect final result.

4. Incorrect Loop Direction in DP Table Construction

Wrong approach:

# Iterating in wrong direction
for i in range(n):
    for j in range(i + 1, n):
        is_palindrome[i][j] = s[i] == s[j] and is_palindrome[i + 1][j - 1]

This fails because when we check is_palindrome[i + 1][j - 1], that value hasn't been computed yet (we're going top-to-bottom, but need values from below).

Correct approach: Iterate from bottom to top (i from n-1 to 0) to ensure required values are computed before being used.