294. Print All Palindromic Partitions of a String

Given a string s, print every way to partition it into one or more contiguous substrings such that every substring is a palindrome. Print each partition on its own line, as its substrings in order separated by single spaces. Generate partitions by trying the shortest valid palindromic prefix first at every step (this also fixes the order the partitions are printed in, matching the example).

Input: A single line containing the string s. Output: Print every palindromic partition of s, one per line, as its substrings separated by single spaces, in shortest-prefix-first order.

1 <= |s| <= 15

Trying the SHORTEST valid palindromic prefix first at every step is exactly what produces the results in the specific order the problem's example expects - a subtle but important detail for matching exact expected output.

Print every possible way to split a string into pieces where each piece is itself a palindrome. Brute force: Generate every possible way to insert cut points across the string, then filter for those where every resulting piece happens to be a palindrome - this generates and discards many invalid candidate partitions rather than only ever building valid ones from the start. Optimised: Checking the palindrome condition BEFORE recursing into a candidate prefix (rather than generating a full partition first and checking afterward) prunes invalid branches immediately, meaning every completed recursive path IS automatically a valid palindromic partition - no post-hoc filtering needed.

Precompute an isPal[i][j] table in O(n^2) up front, where isPal[i][j] is true exactly when s[i] equals s[j] and isPal[i+1][j-1] is true, so any 'is this piece a palindrome' question afterward is an O(1) lookup instead of an O(length) scan. Then run the same shortest-piece-first pruned backtracking as before, but replace every direct palindrome check with a table lookup. Since the number of valid partitions can itself be exponential, the overall time is still driven by that output size, but each individual step of the search becomes O(1) instead of O(n). Time: O(n^2 + 2^n) Space: O(n^2)

Generate every possible way to place cut points among the string's positions, equivalent to choosing any subset of the n-1 gaps between characters, form the resulting list of substrings for each such cut pattern, and check whether every substring in it is a palindrome before printing the valid ones. This tries and fully constructs partitions that are obviously invalid, because an early piece already isn't a palindrome, just as often as it builds valid ones. Time: O(2^n * n) Space: O(n)

Build partitions incrementally with backtracking: at each step, only extend the current partial partition with a next candidate piece if that piece is itself a palindrome, checked directly by scanning inward from both ends, and only recurse further when it is, backing out to try a longer piece otherwise. Trying candidate piece lengths shortest-first at each step both prunes invalid partitions the moment a bad piece would be introduced and naturally produces the partitions in the exact order the problem requires. The worst case is still exponential, since a string of all-identical characters genuinely has exponentially many valid palindromic partitions to print, but far less work is wasted compared to generate-then-validate. Time: O(2^n * n) Space: O(n)

1. Try every possible palindromic PREFIX of the remaining string, shortest first - this fixes the exact order results are printed in. 2. For each valid palindromic prefix found, add it to a running list of chosen pieces, recurse on what remains, then remove it (backtrack) before trying the next candidate prefix. 3. When the remaining string is fully consumed, the running list of pieces IS one complete valid partition - record and print it.

Time: Exponential in the worst case (the number of palindromic partitions itself can be exponential for certain strings), though the small constraint (|s| <= 15) keeps this fully manageable. Space: O(n) for the recursion depth and current partition being built, plus space for all generated partitions.

Test |s| = 1 (single partition, the whole string) and |s| = 15 (largest case, where a repetitive string produces many partitions).

Be ready to connect this directly to the 'count' variant of the same problem - both use the identical recursive structure, differing only in whether you build/print each partition or just increment a counter.