public static ArrayList<String> wordBreak(String s, Set<String> dict) {
		ArrayList<String> results = new ArrayList<String>();
		StringBuilder re = new StringBuilder();
		ArrayList<ArrayList<Integer>> dp = new ArrayList<ArrayList<Integer>>();
		for (int i = 0; i < s.length() + 1; i++) {
			dp.add(new ArrayList<Integer>());
		}
		for (int i = 0; i < s.length(); i++) {
			if (i > 0 && dp.get(i).size() == 0)
				continue;
			for (String e : dict) {
				int end = i + e.length();
				if (end > s.length())
					continue;
				String sub = s.substring(i, end);
				if (sub.equals(e))
					dp.get(end).add(i);
			}
		}
		helper(results, re, s, dict, dp, s.length(), 0);
		return results;
	}