<p>Given a string <code>s</code> and a dictionary of strings <code>wordDict</code>, add spaces in <code>s</code> to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in <strong>any order</strong>.</p>

<p><strong>Note</strong> that the same word in the dictionary may be reused multiple times in the segmentation.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;catsanddog&quot;, wordDict = [&quot;cat&quot;,&quot;cats&quot;,&quot;and&quot;,&quot;sand&quot;,&quot;dog&quot;]
<strong>Output:</strong> [&quot;cats and dog&quot;,&quot;cat sand dog&quot;]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;pineapplepenapple&quot;, wordDict = [&quot;apple&quot;,&quot;pen&quot;,&quot;applepen&quot;,&quot;pine&quot;,&quot;pineapple&quot;]
<strong>Output:</strong> [&quot;pine apple pen apple&quot;,&quot;pineapple pen apple&quot;,&quot;pine applepen apple&quot;]
<strong>Explanation:</strong> Note that you are allowed to reuse a dictionary word.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;catsandog&quot;, wordDict = [&quot;cats&quot;,&quot;dog&quot;,&quot;sand&quot;,&quot;and&quot;,&quot;cat&quot;]
<strong>Output:</strong> []
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 20</code></li>
	<li><code>1 &lt;= wordDict.length &lt;= 1000</code></li>
	<li><code>1 &lt;= wordDict[i].length &lt;= 10</code></li>
	<li><code>s</code> and <code>wordDict[i]</code> consist of only lowercase English letters.</li>
	<li>All the strings of <code>wordDict</code> are <strong>unique</strong>.</li>
	<li>Input is generated in a way that the length of the answer doesn&#39;t exceed&nbsp;10<sup>5</sup>.</li>
</ul>

# Why we need caching ?
# Example :
        
# s = catsandsanddogs
# wordDict = [cat, s, cats, and, sand, dogs]
# consider 2 scenarios: 
#         catsandsanddogs
#         cat | sandsanddogs # first add space after cat , and then after s
#         cat | s | andsanddogs # now we need to find all the words formed from index 4 to the end

#         cats| and sand dogs  # add space after cats . # Again we need to find all the words formed from index 4 to the end. If we had already calculated the possible words that can be formed from i till the end of the array, we could simply reused that list.
# To understand how will we form the array in recurion:
# s= catdogabc
# worddict = [cat, dog, abc, dogabc]
# suppose we initially take the string from i = 0 to j = 2, "cat" which is a valid word.
# Now we need to traverse from i + 1 and find all possible words
# in one scenario we got [dog abc] and in another we got [dogabc]
# w = cat & strings = ["dog abc", "dogabc", ""] 
# ["cat dog abc", "cat dogabc"] # insert w at the start of the string
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        wordDict = set(wordDict)
        # stores key = index and values as a list of all the words formed from index key to the end
        dp = {}
        def traverse(i):
            # Base case: If we've reached the end of the string, return a list with an empty string
            # This indicates we can form a valid sentence till the end
            if i == len(s):
                return [""]

             # Check if result for this index `i` is already computed (memoization)
            if i in dp:
                return dp[i]

            # Initialize an empty result list to store all valid sentences starting from index `i`
            res = []
            for j in range(i, len(s)):
                w = s[i:j+1] # Extract the substring from index `i` to `j`

                # If the substring `w` is not in the word dictionary, skip this iteration
                if w not in wordDict:
                    continue

                # Recursively find valid sentences starting from index `j+1` (next character after the current word)
                # It returns a list of possible valid sentences (strings) formed from index `j+1` to the end
                # it will return a list - either empty or with actual sentences possible from i to N-1
                # Example: w = cat & strings = ["dog abc", "dogabc", ""] 
                # ["cat dog abc", "cat dogabc"] # insert w at the start of the valid string string
                strings = traverse(j+1)

                # if strings is empty, we didnot find any valid sentence that can be formed
                if not strings:
                    continue


                for string in strings:
                    # For each valid sentence returned, prepend the current word `w`
                    # Create new sentences by adding `w` before the sentences from `strings`
                    sentence = w
                    if string:
                        sentence += " " + string
                    res.append(sentence)

            # Store the result for index `i` in the `dp` dictionary (memoization)
            dp[i] = res
            
             # Return the result list of valid sentences for the current index `i`
            # return an empty array when we can't break the string into words
            return res

        return traverse(0)

16500