回溯法 | 单词拆分 ||

class Solution {
    List<String> ss = new ArrayList<>();
    public List<String> wordBreak(String s, List<String> wordDict) {

        dfs(s,wordDict,"",0);

        return ss;
    }
    public void dfs(String s, List<String> wordDict, String res, int idx){
        if(idx==s.length()){
            ss.add(res.trim());
            return;
        }
        //去掉外循环
        for(int j=idx+1;j<=s.length();j++){
            if(wordDict.contains(s.substring(idx,j))){
                int l = res.length();
                res = res + " " + s.substring(idx,j);
                dfs(s,wordDict,res,j);
                res = res.substring(0,l);
            }
        }
        
    }
}