public List<String> wordBreak4(String s, Set<String> dict) {
        int len = s.length();
        List<String> result = new ArrayList<String>();
        if(len == 0) return result;

        List<List<Integer>> list = new ArrayList<List<Integer>>();
        for(int i = 0; i <= len; i++) list.add(new ArrayList<Integer>());

        for(int i = 1; i <= len; i++){
            for(int j = 0; j < i; j++){
                String sub = s.substring(j, i);
                if((j == 0 || list.get(j).size() != 0) && dict.contains(sub)){
                    list.get(i).add(j);
                }
            }
        }

        StringBuilder single = new StringBuilder();
        backtrack4(s, s.length(), list, single, result);
        return result;
    }