time complexity of word break algorithm
If there is one string x that can be parsed in two ways then repeating x n times can be parsed in at least $2^n$ ways. So the problem has either 0, 1, or an exponential number of solutions. Asking for all is likely pointless. 

However, you could provide an answer with many solutions in a much more compact format. Say your input is "catsanddog" repeated 100 times with $2^{100}$ solution, clearly infeasible. Instead we present a solution like this: "word1 word2 word3" if a solution consists of these three words. [solution1 | solution2 | solution3] if there are say three alternatives. And everything concatenated. So the solution in the case above would be written as ["cats and dog" | "cat sand dog"] repeated 100 times. 

In practice, this will usually give a solution with size cN for a not very large c, where N is the input size. You can still have extremes. Take the dictionary ["a", "aa"] and a string of n a's as input. The first few solutions are: 

"a": "a"
"aa": ["a a" | "aa"]
"aaa": ["a aa" | ["a a" | "aa"] "a"]
"aaaa": [["a a" | "aa"] "aa" | ["a aa" | ["a a" | "aa"] "a"] "a"]