public ArrayList<String> wordBreakRec(String s, Trie trie) {

		ArrayList<String> res = new ArrayList<String>();
		ArrayList<Integer> ends = trie.seach(s);
		if (!ends.isEmpty()) {
			for (Integer end : ends) {
				// res.add(s.substring(0, end));
				String strBegin = s.substring(0, end);
				String sTmp = s.substring(end);
				ArrayList<String> strRear = wordBreakRec(sTmp, trie);
				if (strRear.isEmpty()) {
					res.add(strBegin);
				} else {
					for (String str : strRear) {
						res.add(strBegin + " " + str);
					}
				}
			}
		}
		return res;
	}