public ArrayList<String> wordBreak(String s, Set<String> dict) {
		if (s == null || s.length() == 0) {
			return null;
		}
		int len = s.length();
		boolean[] t = new boolean[len + 1];
		t[0] = true;

		for (int i = 0; i < len; i++) {
			if (!t[i])
				continue;
			for (String a : dict) {
				int length = a.length();
				int end = i + length;
				if (end > len)
					continue;
				if (t[end])
					continue;
				if (s.substring(i, end).equals(a)) {
					t[end] = true;
				}
			}
		}
		ArrayList<String> result=new ArrayList<String>();
		if(!t[len])
			return result;
		dfs(s,t,len,0,result,new StringBuilder(),dict);
		return result;
	}