Palindrome Partitioning

Split the string into pieces so that every piece is a palindrome. Print every possible way.

Input: one line s (lowercase letters).

Output:

• line 1: the number of partitions p
• next p lines: one partition each, its pieces in order separated by spaces

List the partitions in lexicographic order, comparing piece by piece (so a a b comes before aa b).

Constraints: 1 ≤ length of s ≤ 16.

Think about it: backtrack over the end of the first piece; recurse on the rest only if the piece is a palindrome. Precomputing isPal[i][j] with DP avoids re-checking the same substrings. Trying shorter first pieces first produces exactly the required order.