Given a string and word dictionary, return all possible sentences by adding spaces.
Sample Input:
"catsanddog", ["cat","cats","and","sand","dog"]
Sample Output:
["cat sand dog","cats and dog"]
Hints
Hint 1
Use recursion with memoization
Hint 2
Try all possible word breaks
Hint 3
Build sentences by combining results
