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

Time limit exceed

public class Solution {
    List<String> res = new ArrayList<>();

    public List<String> wordBreak(String s, Set<String> wordDict) {
        if(s == null || s.length() == 0) return res;
        List<String> list = new ArrayList<String>();
        break2(s, list, wordDict);
        return res;
    }

    void break2(String s, List<String> list, Set<String> dict){
        if(s.length() == 0){
            StringBuilder sb = new StringBuilder();
            sb.append(list.get(0));
            for(int i=1; i< list.size(); i++){
                sb.append(' ');
                sb.append(list.get(i));
            }
            res.add(sb.toString());
            return;
        }

        for(int i=1; i<= s.length(); i++){
            String sub = s.substring(0, i);
            if(dict.contains(sub)){
                list.add(sub);
                break2(s.substring(i), list, dict);
                list.remove(list.size()-1);
            }
        }
    }
}