LeetEye LeetEye
Hard Backtracking ~5 min

Palindrome Partitioning

backtracking 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

Example 1
Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]
Example 2
Input: s = "a"
Output: [["a"]]
Key Insight

At each position, try all possible palindrome prefixes. Then recursively partition the rest.

At each position, try all possible lengths. If s[i:j] is palindrome, take it and partition s[j:]. Add to result when string fully consumed.

How to Approach This Problem

Pattern Recognition: When you see keywords like palindrome partitioning backtracking, think Backtracking.

Step-by-Step Reasoning

1 At position i, we choose:
Answer: How far to extend the current palindrome
We try all possible ending positions j where s[i:j] is a palindrome.
2 We add current partition to result when:
Answer: We've processed the entire string
When start index reaches end of string, we've successfully partitioned everything.
3 We can extend from position i to j if:
Answer: s[i:j+1] is a palindrome
Each piece must be a palindrome. We only proceed if the piece from i to j is valid.
4 After choosing s[i:j] as a piece, we:
Answer: Move to position j and continue
We've used characters 0 to j-1. Now partition the rest starting at j.
5 To check if s[i:j] is a palindrome:
Answer: Compare with reverse
A palindrome reads same forwards and backwards.
6 For string "aaa", the number of valid partitions is:
Answer: 4
["a","a","a"], ["a","aa"], ["aa","a"], ["aaa"]. 4 ways.

Solution

def partition(s: str) -> List[List[str]]:
    result = []
    
    def is_palindrome(sub):
        return sub == sub[::-1]
    
    def backtrack(start, current):
        if start == len(s):
            result.append(current[:])
            return
        
        for end in range(start + 1, len(s) + 1):
            substring = s[start:end]
            if is_palindrome(substring):
                current.append(substring)
                backtrack(end, current)
                current.pop()
    
    backtrack(0, [])
    return result

Complexity Analysis

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

Master This Pattern

Build intuition with interactive MCQs. Practice Backtracking problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye