<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]]:
        output = []

        def _is_palindrome(s):
            for i in range(len(s) // 2):
                if s[i] != s[-i - 1]:
                    return False
            return True

        def dfs(list, start, curr):
            if curr == len(s) - 1 and not _is_palindrome(s[start: curr + 1]):
                return

            if curr == len(s) - 1:
                temp = list.copy()
                temp.append(s[start :])
                output.append(temp)
                return
            # print(f'list: {list}, start: {start}, curr: {curr}')
            # print(f's[start : curr + 1]: {s[start : curr + 1]}')
            # print(f'list.append(s[start : curr + 1]: {list.append([s[start : curr + 1]]).copy()}')
            if _is_palindrome(s[start: curr + 1]):
                temp = list.copy()
                temp.append(s[start : curr + 1])
                dfs(temp, curr + 1, curr + 1)
            dfs(list, start, curr + 1)

        dfs([], 0, 0)
        return output       
37164