拆分词句II

import java.util.*;

public class Solution {
    public ArrayList<String> wordBreak(String s, Set<String> dict) {
        ArrayList<String> list = new ArrayList<>();
        dfs(s, s.length(), "", dict, list);
        return list;
    }

    /**
     * index 末尾索引
     */
    public void dfs(String s, int index, String str, Set<String> dict, List<String> list){
        if(index <= 0){
            if(str.length() > 0){
                list.add(str.substring(0, str.length() - 1));
            }
            return;
        }

        for(int i = index; i >= 0; --i){
            if(dict.contains(s.substring(i, index))){
                dfs(s, i, s.substring(i, index) + " " + str, dict, list);
            }
        }
    }
}