Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
Example 1:
Input: s = "aab" Output: [["a","a","b"],["aa","b"]]
Example 2:
Input: s = "a" Output: [["a"]]
Constraints:
1 <= s.length <= 16s contains only lowercase English letters.Problem Overview: Given a string s, return all possible ways to partition it so every substring in the partition is a palindrome. Each partition must cover the entire string, and the result includes every valid combination.
Approach 1: Recursive Backtracking (O(n * 2^n) time, O(n) space)
The straightforward approach uses backtracking to try every possible cut in the string. Start from index 0, expand the substring one character at a time, and check whether the current segment is a palindrome using two pointers from both ends. If it is, add it to the current path and recursively process the remaining suffix. When the recursion reaches the end of the string, the current path represents a valid partition. This approach explores all partition possibilities, which leads to roughly 2^n combinations in the worst case. Each palindrome check costs O(n), so the total runtime becomes O(n * 2^n). Space complexity is O(n) for the recursion stack and current partition path, excluding output.
Approach 2: Dynamic Programming + Backtracking (O(n * 2^n) time, O(n^2) space)
The bottleneck in the previous method is repeatedly checking whether substrings are palindromes. You can eliminate that repeated work by precomputing palindrome information using dynamic programming. Build a 2D table dp[i][j] where each cell indicates whether the substring s[i..j] is a palindrome. Fill this table by expanding substring lengths: single characters are palindromes, and longer substrings are palindromes if their endpoints match and the inner substring is also a palindrome. This preprocessing costs O(n^2) time and space.
Once the DP table is built, run the same backtracking process. Instead of scanning characters each time, check dp[start][end] in O(1). This avoids repeated substring comparisons and makes the search significantly faster in practice. The recursion still explores up to 2^n partitions, so the overall time complexity remains O(n * 2^n), but with much smaller constant factors.
Recommended for interviews: Interviewers typically expect the backtracking solution first since it naturally models the partition decision process. Demonstrating the DP optimization shows stronger algorithmic thinking because you identify and remove redundant palindrome checks. Starting with brute-force backtracking proves you understand the search space; adding the DP table shows you can optimize repeated work in string problems.
Recursive Backtracking: This approach involves using recursion to explore all possible ways to partition the string. At each position, we check all possible substrings starting from that position, and if a substring is palindrome, we recursively partition the remaining substring. This way, we build possible partitions incrementally.
This Python solution uses a helper function backtrack to perform recursive backtracking. We check each substring from the current position start. If it is a palindrome, we include it in our current path (path) and recursively continue partitioning the remainder of the string. If start reaches the end of the string, we add the current path to the results (res).
Time Complexity: O(2n * n), since we can have 2^n possible partitions and checking each partition takes O(n).
Space Complexity: O(n), where n is the depth of the recursive call stack.
Dynamic Programming with Backtracking: This approach utilizes dynamic programming to precompute whether substrings are palindromes, reducing the on-the-fly palindrome check complexity in backtracking.
This Python solution first uses dynamic programming to fill a table dp where dp[i][j] is True if the substring s[i:j+1] is a palindrome. Then, using backtracking, it generates partitions. If a substring s[start:end+1] is a palindrome (checked in O(1) time using dp), it adds it to the current path and continues recursively until the entire string is partitioned.
Time Complexity: O(n2 + 2n * n). Filling the dp table takes O(n2), and backtracking takes O(2n * n).
Space Complexity: O(n2), required for the dp table.
| Approach | Complexity |
|---|---|
| Recursive Backtracking | Time Complexity: O(2n * n), since we can have 2^n possible partitions and checking each partition takes O(n). |
| Dynamic Programming with Backtracking | Time Complexity: O(n2 + 2n * n). Filling the |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Backtracking | O(n * 2^n) | O(n) | Good starting solution in interviews. Simple to implement and demonstrates understanding of partition search. |
| Dynamic Programming + Backtracking | O(n * 2^n) | O(n^2) | Preferred approach when palindrome checks repeat often. DP table enables O(1) substring validation. |
L17. Palindrome Partitioning | Leetcode | Recursion | C++ | Java • take U forward • 420,666 views views
Watch 9 more video solutions →Practice Palindrome Partitioning with our built-in code editor and test cases.
Practice on FleetCode