Recursion and Backtracking Generating every choice

325. Palindrome Partitioning

You are given a string s of lowercase letters. Cut s into one or more pieces so that every piece is a palindrome, and return every way to do it.

A palindrome reads the same from left to right as from right to left, like "level", "noon" or a single letter. A way is the list of pieces from left to right, and joined together the pieces give s back. Two ways are different when they cut s in different places. A single letter is always a palindrome, so cutting s into its letters always works, and the answer is never empty.

The ways can come back in any order, and any order is accepted. Inside a way, the pieces stay in the order they have in s. The examples sort the ways, comparing them piece by piece.

Example 1

Input: s = "abaab"

Output:

[["a","b","a","a","b"],
 ["a","b","aa","b"],
 ["a","baab"],
 ["aba","a","b"]]

Explanation: Three pieces longer than one letter are palindromes: "aba", "aa" and "baab". Each way uses at most one of them, because any two of them overlap, so there are four ways: the letters alone, and one way for each of the three.

Example 2

Input: s = "dog"

Output: [["d","o","g"]]

Explanation: No two neighbouring letters are equal, and "dog" is not a palindrome. The only way is to cut s into its three letters.

Example 3

Input: s = "aaa"

Output: [["a","a","a"],["a","aa"],["aa","a"],["aaa"]]

Explanation: Every piece of a string of one repeated letter is a palindrome, so every choice of cuts works: two gaps give four ways. ["a","aa"] and ["aa","a"] are different ways, because they cut s in different places.

Check your understanding

Work out the answer for this input before you write any code.

s = "abba"

Constraints

1 ≤ s.length ≤ 16
s holds only lowercase English letters.

Clarifying questions

What you would ask an interviewer before writing any code.