# LeetCode 131: Palindrome Partitioning — Step-by-Step Visual Trace

**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

```python
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

> **[Open interactive visualization](https://tracelit.dev/app?trace=0131_palindrome-partitioning)**

> **Try it yourself:** Open [TraceLit](https://tracelit.dev/app?trace=0131_palindrome-partitioning) and step through every line.

---

*Built with [TraceLit](https://tracelit.dev) — the visual algorithm tracer for LeetCode practice.*