Palindrome Partitioning
Module 16 · Recursion & Backtracking
Problem
Given a string s, partition it so that every substring of the
partition is a palindrome. Return all possible such partitionings.
(LeetCode 131.)
Examples
Example 1
Input
s = "aab"Output[["a","a","b"], ["aa","b"]]Example 2
Input
s = "a"Output[["a"]]Constraints
1 ≤ s.length ≤ 16, lowercase English letters only.
Attempt it first
This is a backtracking problem whose choices aren't "include or exclude an element" (Subsets) or "reuse or not" (Combination Sum) but where to cut: given you're currently at some starting position in the string, how far forward should the next piece extend? Before opening anything, work out: at a given start index, how many different "next cuts" are legal candidates to try, and what has to be true about each candidate substring before it's worth recursing past it?