Problem Statement

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

A palindrome string is a string that reads the same backward as forward.

Additional information

• 1 <= s.length <= 16
• s contains only lowercase English letters.

Example 1:

Input: s = "aab"

Output: [["a", "a", "b"], ["aa", "b"]]

Example 2:

Input: s = "a"

Output: [["a"]]

Brute Force (Generate All Partitions Then Filter)

Intuition

A string of length N has exactly N - 1 "slots" between its characters where we could potentially make a cut. This means there are 2^(N-1) possible ways to partition the string.

A naive approach is to completely ignore the palindrome requirement at first. We simply generate every single possible partition of the string. Once we have a massive list of all possible partitions, we loop through them and throw away any partition that contains a substring that isn't a palindrome.

Algorithm

1. Create a helper function is_palindrome(sub) that checks if a string reads the same forwards and backwards.
2. Create a recursive function get_all_partitions(start) to generate all ways to cut the string from the start index.
3. If start == len(s), return [[]] (a list containing an empty partition).
4. Loop end from start to len(s) - 1.
5. Extract the current substring: prefix = s[start : end + 1].
6. Recursively call get_all_partitions(end + 1) to get all partitions of the remaining suffix.
7. Attach the prefix to the front of every suffix partition and add it to our list of all partitions.
8. Once all partitions are generated, filter the final list: only keep a partition if all(is_palindrome(sub) for sub in partition) is True.

def partition(s: str) -> list[list[str]]:
    def is_palindrome(sub):
        return sub == sub[::-1]
        
    def get_all_partitions(start):
        if start == len(s):
            return [[]]
            
        all_parts = []
        for end in range(start, len(s)):
            prefix = s[start : end + 1]
            suffix_partitions = get_all_partitions(end + 1)
            
            for suffix in suffix_partitions:
                all_parts.append([prefix] + suffix)
                
        return all_parts

    # Generate everything, then filter
    all_possible = get_all_partitions(0)
    res = []
    
    for part in all_possible:
        if all(is_palindrome(sub) for sub in part):
            res.append(part)
            
    return res

Time & Space Complexity

• Time complexity: O(N * 2^N)

• Reason: We generate 2^(N-1) partitions. Generating the arrays takes time, and then we filter them. Checking if all substrings in a partition are palindromes takes O(N) time per partition.

• Space complexity: O(N * 2^N)

• Reason: We are actively storing all 2^(N-1) possible partitions in memory at the same time before filtering them down, which uses a massive amount of auxiliary space.

Recursive Backtracking (DFS) - Optimal

Intuition

We can optimize this massively by pruning bad paths early. Why generate the rest of a partition if the very first chunk we cut off isn't even a palindrome?

We can use Depth-First Search (DFS) to build partitions step-by-step.
We start at the beginning of the string and try cutting a prefix. If and only if that prefix is a palindrome, we add it to our current path and recursively try to partition the rest of the string. If the prefix is not a palindrome, we immediately stop exploring that branch and try a longer prefix.

Algorithm

1. Initialize an empty list res for the final valid partitions.
2. Create a helper function is_palindrome(left, right) to check if s[left:right+1] is a palindrome without creating new string copies.
3. Create a recursive helper dfs(start, current_partition).
4. Base Case: If start >= len(s), we have successfully partitioned the entire string into palindromes. Append a .copy() of current_partition to res and return.
5. Loop & Prune: Start a for loop with end going from start to len(s) - 1.
6. Check if the substring from start to end is a palindrome.
7. If it is a palindrome:

• Append the substring s[start : end + 1] to current_partition.
• Recursively call dfs(end + 1, current_partition).
• Backtrack by popping the substring off current_partition.

8. Call dfs(0, []) and return res.

def partition(s: str) -> list[list[str]]:
    res = []
    
    def is_palindrome(left, right):
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True
        
    def dfs(start, current_partition):
        if start >= len(s):
            res.append(current_partition.copy())
            return
            
        for end in range(start, len(s)):
            # Pruning: Only branch if the current prefix is a palindrome
            if is_palindrome(start, end):
                current_partition.append(s[start : end + 1])
                dfs(end + 1, current_partition)
                current_partition.pop()
                
    dfs(0, [])
    return res

Time & Space Complexity

• Time complexity: O(N * 2^N)

• Reason: In the absolute worst-case scenario (e.g., a string like "aaaaa" where every single possible substring is a palindrome), the decision tree still explores 2^N paths. At each leaf node, we spend O(N) time copying the partition array to the result list. However, for average strings, the aggressive pruning makes this run exponentially faster than the brute-force approach.

• Space complexity: O(N)

• Reason: Excluding the output array, the auxiliary space is strictly bounded by the maximum depth of the recursion stack and the current_partition list. The deepest the recursion goes is the length of the string, O(N).