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

DP + Backtracing, quite like Unique Binary Search Trees II

res = word in Dict + func (subArray)

public List<String> wordBreak(String s, Set<String> wordDict) {

    return helper(s, wordDict, new HashMap());
}

private List<String> helper(String s, Set<String> wordDict, Map<String, List<String>> map){

    if(map.get(s) != null) return map.get(s);

    if(s.length() == 0) return new ArrayList(Arrays.asList(""));

    List<String> res = new ArrayList();

    for(String word : wordDict){

        if(s.startsWith(word)){

            List<String> subArrays = helper(s.substring(word.length()), wordDict, map);

            for(String sub : subArrays){
                res.add(word + (sub.length() == 0 ? "" :" " + sub));
            }
        }
    }

    map.put(s, res);

    return res;
}