public class Solution {
private Set<String> wordDict;
public List<String> wordBreak(String s, Set<String> wordDict) {
List<String> result = new ArrayList<String>();
if (s.length() == 0  wordDict.size() == 0) {
return result;
}
this.wordDict = wordDict;
int maxLength = 0;
for (String str : wordDict) {
maxLength = Math.max(maxLength, str.length());
}
boolean[] possible = new boolean[s.length() + 1];
possible[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = i; j > 0 && i  j + 1 <= maxLength; j) {
if (possible[j  1] && wordDict.contains(s.substring(j  1, i))) {
possible[i] = true;
break;
}
}
}
System.out.println(possible[s.length()]);
if (!possible[s.length()]) {
return result;
}
List<String> list = new ArrayList<String>();
helper(s, 0, possible, list, result);
return result;
}
private void helper(String s, int index, boolean[] possible, List<String> list, List<String> result) {
if (index == s.length()) {
StringBuilder sb = new StringBuilder();
for (String str : list) {
sb.append(str);
sb.append(" ");
}
sb.deleteCharAt(sb.length()  1);
result.add(sb.toString());
return;
}
if (!possible[index]) {
return;
}
for (int i = index; i < s.length(); i++) {
if (!wordDict.contains(s.substring(index, i + 1))) {
continue;
}
list.add(s.substring(index, i + 1));
helper(s, i + 1, possible, list, result);
list.remove(list.size()  1);
}
}
}
Java Solution DP + DFS (Beats 91.10%)


@ajak6 Dynamic Programming can prevent us from searching the same intermediate state again and again. Think of one simple input "aaaaaaa...(a lot of a)..aaaaa", you can println the intermediate result and take a look at it. And then you will find using only single DFS is a waste.
Time complexity of DP is O(mn) in which m is the max string length is dict and n is the size of dict and space complexity is O(m) m is the size of string.
So in total, the time complexity would be O(mn^2). However, with result saved in dp array, we can stop early in search when we find it is impossible.
Also you can check these posts to find more information.
https://discuss.leetcode.com/topic/17841/gettingridoftle/2
https://discuss.leetcode.com/topic/8007/pleaseaddtestcasebaaaaaaaaaaaaaaaaaaaaaaa/3
And you can also provided your code here and I am glad to take a look.