<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]]:
        length = len(s)
        val = [[None] * length for _ in range(length)]

        def valid(l0, r0):
            if val[l0][r0] is not None:
                return val[l0][r0]
            l, r = l0, r0
            while l < r:
                if s[l] != s[r]:
                    val[l][r] = False
                    return False
                l += 1
                r -= 1
            val[l0][r0] = True
            return True
        
        dp = [None for _ in range(length)]
        def helper(r):
            if r < 0:
                return [[]]
            if r == 0:
                return [[s[0]]]
            if dp[r] is not None:
                return dp[r]
            out = []
            for l in range(r, -1, -1):
                if valid(l, r):
                    ss = s[l:r + 1]
                    for ls in deepcopy(helper(l - 1)):
                        ls.append(ss)
                        out.append(ls)
            dp[r] = out
            return out
        
        out = helper(length - 1)
        return out
35738