题目链接：https://oj.leetcode.com/problems/word-break-ii/

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"].

思路：还是DFS递归遍历。采用动态规划比较麻烦，需要存储当前位置能够实现 word break的所有结果的和，空间复杂度很高，不划算，代码写起来还很麻烦。

public class Solution {
    public List
  
    wordBreak(String s, Set
   
     dict) { List
    
      rsList = new ArrayList
     
      (); if (s == null || s.length() < 1 || dict == null) { return rsList; } wordBreakHelper(s, 0, "", dict, rsList); return rsList; } public void wordBreakHelper(String s, int start, String tempStr, Set
      
        dict, List
       
         rsList) { if (start >= s.length()) { rsList.add(tempStr); return; } for (int i = start + 1; i <= s.length(); i++) { String temp = s.substring(start, i); if (dict.contains(temp)) { String newTempStr; if (tempStr.length() < 1) { newTempStr = temp; } else { newTempStr = tempStr + " " + temp; } wordBreakHelper(s, i, newTempStr, dict, rsList); } } } }