<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 rec(dp,s, j, mem):
            if j == len(s):
                return []

            if j in mem:
                print("returingin from mem")
                return mem[j]

            res = []

            for i in range(len(dp)):
                if dp[i][j] != 1:
                    continue

                prefix = s[j:j+i+1]
                print("Prefix", prefix)
                if j+i+1 == len(s):
                    res.append([prefix])
                
                else:
                    child_ways = rec(dp, s, j+i+1, mem)
                    print(prefix, child_ways, i, j)
                    if len(child_ways) > 0:
                        for child_way in child_ways:
                            arr=[prefix]
                            arr.extend(child_way)
                            res.append(arr)
        
            mem[j] = res
            print("mem", mem)

            return res
        
        dp = [[0] * len(s) for _ in range(len(s))]
        dp[0] = [1] * len(s) # every substring of single character is a palindrome

        # Every substring of two character length is a palindrome if the first and second character are the same.
        for i in range(len(s) - 1):
            if s[i] == s[i+1]:
                dp[1][i] = 1

        
        for size in range(2, len(s)):

            for j in range(len(s) - size):
                end = j + size
                if s[j] != s[end]:
                    continue
                
                if dp[size - 2][j+1] == 1:
                    dp[size][j] = 1
        print(dp)
        return rec(dp, s, 0, {})
    

38183