from typing import List
from collections import deque
class Solution:
  def wordBreak(self, s: str, wordDict: List[str]) -> bool:
    dp = [[] for _ in range(len(s)+1)]
    dp[0].append('')
    
    for i in range(len(s)):
      for j in range(i+1, len(s)+1):
        if len(dp[i]) != 0 and s[i:j] in wordDict:
          for comb in dp[i]:
            if comb == "":
              dp[j].append(s[i:j])
            else:
              dp[j].append(comb + " " + s[i:j])
    return dp[-1]
    
    ## MEMOIZATION
    # mem = {}
    # mem[''] = ['']
    # def wordBreakH(s):
    #   if s in mem:
    #     return mem[s]
    #   mem[s] = []
    #   for word in wordDict:
    #     if s.startswith(word):
    #       for comb in wordBreakH(s[len(word):]):
    #         if comb == "":
    #           mem[s].append(word)
    #         else:
    #           mem[s].append(word + " " + comb)
    #   return mem[s]
    # return wordBreakH(s)
          
    # res = []
    # queue = deque()
    # for word in dp[len(s)][1]:
    #   queue.append([word, '', len(s)])
    # while queue:
    #   curWord, soFar, curInd = queue.popleft()
    #   soFar = " ".join([curWord, soFar])
    #   nextInd = curInd-len(curWord)
    #   if nextInd == 0:
    #     res.append(soFar.strip())
    #   else:
    #     for nextWord in dp[nextInd][1]:
    #       queue.append([nextWord, soFar, nextInd])
    # return res

sol = Solution()
s = "catsanddog"
wordDict = ["cat","cats","and","sand","dog"]
print(sol.wordBreak(s, wordDict))