<p>Given a string <code>s</code>, partition <code>s</code> such that every <span data-keyword="substring-nonempty">substring</span> of the partition is a <span data-keyword="palindrome-string"><strong>palindrome</strong></span>. Return <em>all possible palindrome partitioning of </em><code>s</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> s = "aab"
<strong>Output:</strong> [["a","a","b"],["aa","b"]]
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> s = "a"
<strong>Output:</strong> [["a"]]
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 16</code></li>
	<li><code>s</code> contains only lowercase English letters.</li>
</ul>

class Solution:

    def partition(self, s: str) -> List[List[str]]:

        def is_palindrome(word):
            l = 0
            r = len(word) - 1
            while l <= r:
                if word[l] != word[r]:
                    return False
                l += 1
                r -= 1
            return True

        def all_palindromes(word):
            ret = []
            for i in range(1, len(word) + 1):
                section = word[0:i]
                rest = word[i:]
                if is_palindrome(section):
                    if len(rest):
                        rest_palindromes = all_palindromes(rest)
                        for other in rest_palindromes:
                            # print(section, rest_palindromes, [section] + other)
                            ret.append([section] + other)
                    else:   
                        ret.append([section])
            return ret

        return all_palindromes(s)
28810