Palindrome Partitioning

Problem

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

Examples

The brute-force approach

Try all ways to split the string into substrings. For each split, check if all parts are palindromes.

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

O(n × 2^n) — exponential number of partitions, each with an O(n) palindrome check.

Spotting the pattern

This is a Backtracking problem. The key question to ask yourself:

At index start, you try all possible ending positions. When you find a palindrome s[start:end], you recurse from end. What guarantees every part of the final path is a palindrome?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.