Palindrome Partitioning

Given a nonempty lowercase English string s, return every way to split it into contiguous, nonempty substrings such that each substring is a palindrome.…

Given a nonempty lowercase English string s, return every way to split it into contiguous, nonempty substrings such that each substring is a palindrome. Preserve the original order of pieces within each partition; joining them must reproduce s exactly. Return each partition once. The outer order of partitions does not matter.

- 1 <= s.length <= 16. - Every character is an English lowercase letter from 'a' through 'z'. - Every piece is nonempty and reads the same forwards and backwards. - The order of pieces within a partition matters; only the outer result order is arbitrary.

Example 1: input s = "aab"; output [["a","a","b"],["aa","b"]]. Either split the first two letters or keep their palindrome aa, then append b.

Example 2: input s = "ab"; output [["a","b"]]. The complete string ab is not a palindrome. Reversing its pieces would no longer reconstruct the input.

Example 3: input s = "aaa"; output [["a","a","a"],["a","aa"],["aa","a"],["aaa"]]. The middle two partitions have different piece boundaries and order, so both must remain.

Category: Recursion. Topic: recursion. Difficulty: Hard. Patterns: backtracking.