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, split it into substrings such that every substring is a palindrome. Return all possible palindrome partitionings. Each partition must cover the entire string, and substrings must remain in order.
Approach 1: Recursive Backtracking (O(n^2 * 2^n) time, O(n) space)
This approach explores every possible way to cut the string. Starting at index 0, iterate through all possible end positions and check whether s[start:end] forms a palindrome. If it does, add it to the current path and recursively continue partitioning the remaining suffix. The recursion builds a tree where each branch represents one valid split. Palindrome checking takes O(n), and since the recursion may explore up to 2^n partitions, the total cost becomes O(n^2 * 2^n). This approach is straightforward and demonstrates mastery of backtracking with string validation.
Approach 2: Dynamic Programming + Backtracking (O(n^2 + n * 2^n) time, O(n^2) space)
Repeated palindrome checks slow down the pure backtracking solution. Precompute a DP table dp[i][j] where each entry indicates whether substring s[i:j] is a palindrome. Build this table in O(n^2) using the relation: characters at both ends must match and the inner substring must also be a palindrome. Once the table is ready, run the same backtracking procedure but replace the palindrome check with a constant-time lookup. This reduces redundant work and keeps the recursive exploration focused only on valid splits.
The DP table integrates naturally with the recursion: at each index, iterate through possible end positions and continue only if dp[start][end] is true. This combination of dynamic programming and backtracking avoids repeated substring scans while still generating every valid partition. Memory usage increases to O(n^2) for the table, but runtime becomes significantly faster for longer strings.
Recommended for interviews: The DP + backtracking solution is the expected approach. Interviewers want to see you first model the search space with backtracking, then optimize repeated palindrome checks using string DP preprocessing. Starting with the brute-force recursion shows you understand the structure of the problem; adding the DP table demonstrates optimization and algorithmic maturity.
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).
Java
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.
C++
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 * 2^n) | O(n) | Best for understanding the recursion tree and brute-force partition generation |
| DP + Backtracking | O(n^2 + n * 2^n) | O(n^2) | Preferred solution when repeated palindrome checks become expensive |
L17. Palindrome Partitioning | Leetcode | Recursion | C++ | Java • take U forward • 324,255 views views
Watch 9 more video solutions →Practice Palindrome Partitioning with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor