Given a string and a word dict, find all possible sentences
I have figured out how to do this problem and achieve the time and space requirements. It is faster than 64% of submissions but only more space efficient than 5% of submissions (woops). I ended up modifying the code that fails the space requirements. Here is my solution:

class Solution:
    def wordBreak(self, s: str, wordDict: 'List[str]') -&gt; 'List[str]':
        from collections import defaultdict

        if not wordDict:
            return []

        wD = set(wordDict)
        childs = defaultdict(list)
        childs[len(s)] = [None]

        for i in range(len(s) - 1, -1, -1):
            for j in range(i + 1, len(s) + 1):
                if s[i:j] in wD and j in childs:
                    childs[i].append(j)

        paths = []

        def dfs(nd, path):
            if nd is None:
                paths.append(path)
                return

            for ch in childs[nd]:
                dfs(ch, ' '.join([path, s[nd:ch]]))

        dfs(0, '')
        return [x.strip() for x in paths]


Any optimizations are still welcome.