Backtracking
Choosing where to cut
The choice is not which item to take, but where the next piece ends.
Key idea
The shape
For problems about breaking a sequence into consecutive pieces, each level of the search chooses where the current piece ends. The loop runs over possible end positions rather than over items.
You wrote this in the first lab of this unit. Adding a condition on which pieces are allowed turns it into a constrained search, and the condition is where the pruning goes.
Tip
`break` rather than `continue`
Because end only increases, once a piece is too long every later one is too. So break is correct and continue would merely be slower.
Spotting when a rejection means abandon the whole loop rather than skip this one is a small habit that removes real work. It applies whenever the loop variable moves monotonically and the rejection condition is monotone in it.
Cost
Cost, and where it goes
Without constraints, a string of length n has 2 to the n minus 1 ways to split, because each of the n minus 1 gaps is independently a cut or not. So the search is exponential and that is unavoidable when every split is wanted.
Each piece test costs the length of the piece, so testing a property of every piece adds a factor of n. Quoting O(n times 2 to the n) is the expected answer for this family.
Key idea
When the constraint test is expensive
Checking a property of text[start:end] inside the loop repeats work across branches, because the same piece appears under many different prefixes.
Precomputing the answer for every pair of positions, once, removes that repetition. For a property like reading the same forward and backward, a table of which ranges qualify can be filled in O(n squared) and then every check is constant.
That is a genuine optimization worth mentioning even if you do not implement it, and the table it builds is a dynamic programming table, which is a preview of Unit 15.
Predict the output: which cuts are even worth trying
At each position the search may cut after any number of characters, and most of those cuts lead nowhere. Type the four lines it prints.
Palindrome Partitioning
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.