Medium — Backtracking | String | Dynamic Programming | Recursion

The Problem

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

Approach

Uses backtracking to explore all possible ways to partition the string. For each position, tries all possible substrings starting from that position, checks if each substring is a palindrome, and recursively partitions the remaining string.

Time: O(N × 2^N) · Space: O(N)

Code

class Solution:
 def partition(self, s: str) -> List[List[str]]:
 def is_palindrome(sub):
 return sub == sub[::-1]

 def backtrack(start, partition):
 if start == len(s):
 result.append(partition[:]) # Append a copy of the current partition
 return

 for end in range(start + 1, len(s) + 1):
 sub = s[start:end]
 if is_palindrome(sub):
 partition.append(sub)
 backtrack(end, partition)
 partition.pop() # Backtrack

 result = []
 backtrack(0, [])
 return result

Watch It Run

👁 Watch the algorithm run step by step

👁 Watch the algorithm run step by step

Open interactive visualization

Try it yourself: Open TraceLit and step through every line.

Built with TraceLit — the visual algorithm tracer for LeetCode practice.