> For the complete documentation index, see [llms.txt](https://lei-d.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lei-d.gitbook.io/leetcode/backtracking/131palindrome-partitioning.md).

# 131\_ Palindrome Partitioning

\[Medium]\[String, Backtracking]

Given a string *s*, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of *s*.

**Example:**

```
Input: "aab"

Output:
[
  ["aa","b"],
  ["a","a","b"]
]
```

## Solution:

**Idea**:

* Focus on the first possible palindromic string in a partition. 
  * The first string itself is a valid palindromic partition.
  * Do a linear search to find all the possible palindromic substring starting from the first letter.
* Use recursion to deal with the left over. 

**Time Complexity**: $$O(n 2^n)$$ according to EPI page 236

**Space Complexity**: no extra space except for the output

```python
def partition(s):
    """
    :type s: str
    :rtype: List[List[str]]
    """
    def helper(offset, partial):
        # offset is the position of current string we are dealing with
        # partial is the substring that are already partitioned

        if offset == len(s):
            output.append(list(partial))  # list is not neccesary here
            return

        # case when s[offset] is partitioned
        helper(offset+1, partial+[s[offset]])

        # find the next palindrome candidate
        for i in range(offset+1, len(s)):
            if s[i] == s[offset]:
                if s[offset:i+1] == s[offset:i+1][::-1]:
                    helper(i+1, partial+[s[offset:i+1]])

    output = []
    helper(0, [])
    return output
```