public ArrayList<String> wordBreak(String s, Set<String> dict) {
		ArrayList<String> res = new ArrayList<String>();
		Map<Integer, ArrayList<Integer>> pos2word = new HashMap<Integer, ArrayList<Integer>>();
		boolean[] reachable = new boolean[s.length() + 1];
		reachable[0] = true;
		int maxLen = 0;
		
		for(String word : dict) {
			if(word.length() > maxLen) maxLen = word.length();
		}
		
		for(int i = 0; i < s.length(); i++) {
		    if(reachable[i]) {
		        for(int j = i + 1; j <= s.length() && j <= i + maxLen; j++) {
		            String temp = s.substring(i, j);
			        if(dict.contains(temp)) {
			            reachable[j] = true;
			            if(pos2word.containsKey(j)) {
			                pos2word.get(j).add(i);
			            } else {
			                ArrayList<Integer> list = new ArrayList<Integer>();
			                list.add(i);
			                pos2word.put(j, list);
			            }
			        }
		        }
		    }
		}
		
		if(!reachable[s.length()]) return res;
		
		tryNext(res, s, s.length(), new ArrayList<String>(), pos2word);
		return res;
	}