Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

输入描述:

s ="catsanddog"dict ="cat", "cats", "and", "sand", "dog"

输出描述:

[cats and dog, cat sand dog]