LeetCode #131 Medium

Palindrome Partitioning

Split string s into pieces so every piece is a palindrome; return all such partitions.

backtrackingstringdp

02

Intuition

💡

Choose the first piece, then the rest of the string is the same problem again. At each position try every palindromic prefix, recurse on the remainder, and backtrack. The palindrome check prunes whole subtrees the moment a prefix isn't one.

03

Approach

1

Frame as choices at a cut point

From index start, every end where s[start:end+1] is a palindrome is a legal next piece.

2

Recurse and backtrack

Append the piece, recurse from end+1; when start reaches the end of the string the path is one complete answer. Pop and try the next cut.

3

Prune early

Non-palindromic prefixes are never extended — the check happens before recursion, keeping the tree small.

04

Solution & live demo

python

▶1class Solution:
▶2    def partition(self, s):
▶3        res, path = [], []
▶4        def is_pal(a, b):
▶5            while a < b:
▶6                if s[a] != s[b]: return False
▶7                a += 1; b -= 1
▶8            return True
▶9        def backtrack(start):
▶10            if start == len(s):
▶11                res.append(path[:]); return
▶12            for end in range(start, len(s)):
▶13                if is_pal(start, end):
▶14                    path.append(s[start:end+1])
▶15                    backtrack(end + 1)
▶16                    path.pop()
▶17        backtrack(0)
▶18        return res

05

Edge cases

Single character

Every 1-char string is a palindrome → [[c]].

All same letters, e.g. "aaa"

Every cut works — output size grows exponentially; that's inherent to the problem.

06

Complexity

Time

O(n · 2ⁿ)

Space

O(n)

Up to 2ⁿ⁻¹ partitions; recursion depth n.