题目的tag是DP，看了别人答案，确实用DFS解更好一些。

public class Solution {
    public List<String> wordBreak(String s, Set<String> wordDict) {
        return helper(s, new HashMap<String, List<String>>(), wordDict);
    }
    
    public List<String> helper(String s, Map<String, List<String>> map, Set<String> wordDict) {
        if(map.containsKey(s)) {
            return map.get(s);
        }
        List<String> list = new LinkedList<String>();
        if(s.length()==0) {
            list.add("");
            return list;
        }
        
        for(String word : wordDict) {
            if(s.startsWith(word)) {
                List<String> result = helper(s.substring(word.length()), map, wordDict);
                for(String part : result) {
                    list.add(word + (part.length()==0? "":" ") + part);
                }
            }
        }
        
        map.put(s, list);
        return list;
    }
}