Palindrome Partitioning

Given a string s, return every possible partition of s such that every substring in the partition is a palindrome.

For this question, keep the output deterministic: list partitions in the natural depth-first search order created by scanning the next cut from left to right (shorter next piece before longer next piece at the same position). Inside each partition, substrings must stay in their original left-to-right order.

Input / output

• Input: s: string
• Output: string[][] in DFS order

Examples

1. s = "aab" returns [["a","a","b"],["aa","b"]].
2. s = "a" returns [["a"]].
3. s = "efe" returns [["e","f","e"],["efe"]].

Constraints

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

Target complexity

• Aim for O(n * 2^n) time overall, dominated by the number of valid partitions and copied output strings, with O(n^2) preprocessing if you cache palindrome checks.

Hints

1. Try every possible next cut, but only recurse on a substring if it is a palindrome.
2. Rechecking whether the same substring is a palindrome many times is wasteful; precompute a palindrome table or memoize those checks.

Follow-up How would you change the solution if you only needed the minimum number of cuts instead of all valid partitions?