text: class Solution(object):
      def wordBreak(self, s, wordDict):
          """
          :type s: str
          :type wordDict: Set[str]
          :rtype: List[str]
          """
          if not s:
              return []
          # dp[i] means first i letters can be formed by words in the dictionary
          dp = [False] * (len(s)+1)
          dp[0] = True
          for i in range(len(s)+1):
              if dp[i]:
                  for word in wordDict:
                      l = len(word)
                      if i+l < len(dp) and s[i:i+l] == word:
                          dp[i+l] = True
          if not dp[-1]: return []
          
          cur = []
          res = []
          self.helper(cur,res, wordDict,s)
          return res
      
      def helper(self, cur, res, d, s):
          if not s:
              res.append(' '.join(cur))
              return
          for word in d:
              l = len(word)
              if l <= len(s) and s[:l] == word:
                  cur.append(word)
                  self.helper(cur, res, d,s[l:])
                  cur.pop(-1)