public List<String> wordBreak_naive(String s, Set<String> dict) {
        ArrayList<ArrayList<String>> results = new ArrayList<ArrayList<String>>();
        if (s == null) {
            return new ArrayList<String>();
        }
        if (dict == null || dict.size() == 0) {
            return new ArrayList<String>();
        }

        ArrayList<String> list = new ArrayList<String>();
        list.add("");
        results.add(list);
        
        for (int i = 1; i <= s.length(); i++) {
            for (int j = i; j >= 1; j++) {
                if (dict.contains(s.substring(j-1, i))) {
                    ArrayList<String> newList = new ArrayList<String>();
                    for (String str : results.get(j-1)) {
                        newList.add(str + s.substring(j-1, i) + " ");
                    }
                    results.add(newList);
                }
            }
        }
        
        ArrayList<String> re = new ArrayList<String>();
        for (String str : results.get(s.length())) {
            re.add(str.trim());
        }
        
        return re;
    }