<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 isP(word):

        return word == word[::-1]
      

      # find all substrings then check if isP
      ret = []
      def help(path, cw, ind):
        if ind >= len(s):
          # if isP(cw):
          #   path.append(cw)
          if path and len(cw) == 0: 
            ret.append([''.join(row) for row in path])
          return 
        tempWord = cw+s[ind]
        if isP(tempWord):
          # if the word + char is pal, then can include it in partition
          help(path+[[tempWord]], '', ind+1)
        help(path, cw+s[ind], ind+1)
      
      help([], '', 0)
      return ret



        
36349