public static List<String> wordBreak2(String s, Set<String> dict) {
    	int len = s.length();
    	List<List<String>> res = new ArrayList<List<String>>();
    	boolean[] iswordbreak = new boolean[len + 1];
    	iswordbreak[len] = true;
    	for (int i = 0; i < s.length() + 1; i++) {
    		res.add(new ArrayList<String>());
    	}
    	for (int i = len - 1; i >= 0; i--) {
    		for (int j = i; j < len; j++) {
    			String word = s.substring(i, j + 1);
    			if (iswordbreak[j + 1] && dict.contains(word)) {
    				iswordbreak[i] = true;
    				if (0 == res.get(j + 1).size()) res.get(i).add(word);
    				else {
    					for (String str : res.get(j + 1)) {
    						res.get(i).add(word + " " + str);
    					}
    				}
    			}
    		}
    	}
        return res.get(0);
    }