Palindrome Partitioning

At every position in s, decide where the next cut goes: try every prefix of the remaining string, keep it only if that prefix is itself a palindrome, and recurse on what is left. A full partition is found once the whole string has been consumed.

Brute Force: All Cut Combinations, Filter After

Time O(2^n · n)Space O(2^n · n)

A string of length n has n - 1 gaps between characters, each either “cut here” or “no cut” — 2^(n-1) ways total. Generate every combination of cuts, slice the string accordingly, and keep only the partitions where every piece happens to be a palindrome.

class Solution:
    def partition(self, s: str) -> list[list[str]]:
        n = len(s)
        result = []

        def is_palindrome(sub):
            return sub == sub[::-1]

        def build(cuts):
            pieces = []
            start = 0
            for cut in cuts:
                pieces.append(s[start:cut])
                start = cut
            pieces.append(s[start:])
            if all(is_palindrome(p) for p in pieces):
                result.append(pieces)

        def choose_cuts(gap, chosen):
            if gap == n:
                build(chosen)
                return
            choose_cuts(gap + 1, chosen)              # no cut at this gap
            choose_cuts(gap + 1, chosen + [gap])       # cut at this gap

        choose_cuts(1, [])
        return result

Explores all 2^(n-1) cut patterns regardless of whether an early piece is already not a palindrome — e.g. it still finishes building ["aa","b"]-style attempts even when the first character alone already fails.

Backtracking: Only Extend Valid Palindromic Prefixes

OptimalTime O(n · 2^n)Space O(n)

Instead of choosing all cuts up front, grow the partition one piece at a time: from the current position, try every possible next piece (s[start:end] for each end), and only recurse into it if it is a palindrome. Invalid prefixes are abandoned immediately instead of being carried through to the end.

class Solution:
    def partition(self, s: str) -> list[list[str]]:
        n = len(s)
        result = []
        path = []

        def is_palindrome(sub):
            return sub == sub[::-1]

        def backtrack(start):
            if start == n:
                result.append(path[:])
                return
            for end in range(start + 1, n + 1):
                piece = s[start:end]
                if is_palindrome(piece):
                    path.append(piece)
                    backtrack(end)
                    path.pop()

        backtrack(0)
        return result

Tracing s = "aab" as a decision tree — a node is only created if the piece it represents is a palindrome, so "aab" and "ab" are never explored at all:

start=0

1 / 7

resultcurrentdiscarded

Start at index 0. Try every prefix of the remaining "aab": "a", "aa", "aab".

Complexity: in the worst case (e.g. all-identical characters like "aaaa...a"), nearly every one of the 2^(n-1) cut patterns is a valid partition, and building each one costs O(n) → O(n · 2^n) time. Checking whether a substring is a palindrome costs O(n) itself in this simple version, so a tighter bound also needs to account for that — a common optimization precomputes palindrome status for all substrings with O(n^2) DP so each check is O(1). Recursion depth and path are bounded by n → O(n) auxiliary space.