A sign painter cuts a word s into consecutive pieces so that every piece reads the same forwards and
backwards (a palindrome). Return every possible way to cut the word, each as the list of pieces in
their original order. The different cuttings may be returned in any order.
Examples
Input: s = "noon"
Output: [["n", "o", "o", "n"], ["n", "oo", "n"], ["noon"]]
Input: s = "ab"
Output: [["a", "b"]]
Input: s = ""
Output: [[]]
Constraints
0 <= len(s) <= 12, lowercase letters only
Goals
- Partition a string by choosing the end of the next piece
- Only recurse after a piece passes the palindrome test