题目地址：

题目解析：看到题目的第一思路是采用递归暴力解法，每找到一个单词将单词添加到返回的结果集中，并将查找的开始位置后移直到字符串的结尾。

题目解答：

import java.util.HashSet;import java.util.LinkedList;import java.util.List;import java.util.Set;public class Solution {    public List
     
       wordBreak(String s, Set
      
        wordDict) {        List
       
         res = new LinkedList
        
         ();        if(s == null || s.length() == 0){            return res;        }                wordBreak(s, 0, new StringBuilder(), wordDict, res);                return res;    }        private void wordBreak(String s,int start,StringBuilder temp,Set
         
           dict,List
          
            ret){ if(start>=s.length()){ ret.add(temp.toString()); return; } int len = temp.length(); for(int i=start;i
          
         
        
       
      
     

这个解法的思路很简单，但是中间有很多重复的步骤，而且这些重复的步骤有有很多字符串操作比较费时，故考虑先使用动态规划找到能break的点，然后以能break点来遍历找到所有break的路径，解答如下：

import java.util.HashSet;import java.util.LinkedList;import java.util.List;import java.util.Set;public class Solution {    public static List
     
       wordBreak(String s, Set
      
        dict) {        if (s == null || s.length() == 0 || dict == null) {            return null;        }                List
       
         ret = new ArrayList
        
         ();                List
         
           path = new ArrayList
          
           (); int len = s.length(); boolean[] D = new boolean[len + 1]; D[len] = true; for(int i=len-1;i>=0;i--){ D[i] = false; for(int j=i;j
           
             dict, List
            
              path, List
             
               ret, int index, boolean canBreak[]) { int len = s.length(); if (index == len) { StringBuilder sb = new StringBuilder(); for (String str: path) { sb.append(str); sb.append(" "); } sb.deleteCharAt(sb.length() - 1); ret.add(sb.toString()); return; } if (!canBreak[index]) { return; } for (int i = index; i < len; i++) { String left = s.substring(index, i + 1); if (dict.contains(left)) { path.add(left); dfs(s, dict, path, ret, i + 1, canBreak); path.remove(path.size() - 1); } } }}