Description
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.
Example
Example 1:
Input："lintcode"，["de","ding","co","code","lint"]
Output：["lint code", "lint co de"]
Explanation：
insert a space is "lint code"，insert two spaces is "lint co de".
Example 2:
Input："a"，[]
Output：[]
Explanation：dict is null.
思路：
优化方案1
用 Word Break 这个题的思路，使用 is_possible[i] 代表从 i 开始的后缀是否能够被 break，在 DFS 找所有方案的时候，通过 is_possible 可以进行可行性剪枝.
优化方案2
直接使用 memo[i] 记录从位置 i 开始的后缀，能够被 break 出来的所有方案
代码：
优化方案一：
自己写的，可能有点笨。
优化方案2
