https://leetcode.com/problems/word-break-ii


Runtime: 31 ms, faster than 82.58% of Python3 online submissions for Word Break II.

Memory Usage: 13.8 MB, less than 94.90% of Python3 online submissions for Word Break II.


```python
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        #6:53
        possibilities = []
        def try_it(sentenceLeft, trace_list):
            if len(sentenceLeft) == 0:
                possibilities.append(" ".join(trace_list))
                return
            
            found = False
            for word in wordDict:
                if sentenceLeft.startswith(word):
                    found = True
                    new_trace_list = trace_list.copy()
                    new_trace_list.append(word)
                    try_it(sentenceLeft[len(new_trace_list[-1]):], new_trace_list)
        try_it(s, [])
        return possibilities
        #6:59
```