@@ -0,0 +1,1312 @@
+package leetcode.word_break_ii;%0A%0Aimport java.util.ArrayList;%0Aimport java.util.Arrays;%0Aimport java.util.HashSet;%0Aimport java.util.Set;%0A%0Apublic class Solution %7B%0A%09public boolean wordBreak(boolean%5B%5D impossible, ArrayList%3CString%3E ans, char%5B%5D chars, int start, int end, Set%3CString%3E dict, String prefix, StringBuilder sb) %7B%0A%09%09int len = end - start;%0A%09%09if(len == 0)%7B%0A%09%09%09ans.add(sb.toString());%0A%09%09%09return true;%0A%09%09%7D%0A%09%09boolean ret = false;%0A%09%09for(int i = len; i %3E= 0; i--)%7B%0A%09%09%09String w = new String(chars, start, i);%0A%09%09%09if(dict.contains(w) && (i == len %7C%7C !impossible%5Bstart + i%5D))%7B%0A%09%09%09%09int prevLength = sb.length();%0A%09%09%09%09sb.append(prefix);%0A%09%09%09%09sb.append(w);%0A%09%09%09%09if(wordBreak(impossible, ans, chars, start + i, end, dict, %22 %22, sb))%7B%0A%09%09%09%09%09ret = true;%0A%09%09%09%09%7Delse%7B%0A%09%09%09%09%09impossible%5Bstart + i%5D = true;%0A%09%09%09%09%7D%0A%09%09%09%09sb.setLength(prevLength);%0A%09%09%09%7D%0A%09%09%7D%0A%09%09return ret;%0A%09%7D%0A%0A%09public ArrayList%3CString%3E wordBreak(String s, Set%3CString%3E dict) %7B%0A%09%09ArrayList%3CString%3E ans = new ArrayList%3CString%3E();%0A%09%09if(dict.size() == 0) return ans;%0A%09%09wordBreak(new boolean%5Bs.length()%5D, ans, s.toCharArray(), 0, s.length(), dict, %22%22, new StringBuilder());%0A%09%09return ans;%0A%09%7D%0A%0A%09public static void main(String%5B%5D args)%7B%0A%09%09Set%3CString%3E input = new HashSet%3CString%3E(Arrays.asList(new String%5B%5D%7B%22a%22,%22aa%22%7D));%0A%0A%09%09System.err.println(new Solution().wordBreak(%22aaaaa%22, input));%0A%09%7D%0A%7D

Add java solution for 140. Word Break II