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.
For example, given
s ="catsanddog",
dict =["cat", "cats", "and", "sand", "dog"].A solution is
["cats and dog", "cat sand dog"].
DP || DFS + pruning
这题的testcase是在最后设置bug，所以pruning works。同理，如果从后往前做dp，也能轻易通过
剪枝：对可能进行的调用标记值，为dp的一种变形
使用int替换string省空间复杂度
stringstream matters!
succ =succ || wordBreak(s, dict, start + i + 1, cur, res, cut);
影响流程的||和&&不要随便写，短路效应很可怕。一旦succ一次，后面的不再尝试。