idea is same as the bfs one: https://discuss.leetcode.com/topic/2545/a-solution-using-bfs/15

DFS perform very well for "true" results. But in "false" cases it will traverse the whole tree.

Prune the visited false branches will help.

Idean came from work break 2: https://discuss.leetcode.com/topic/27855/my-concise-java-solution-based-on-memorized-dfs

```
public boolean wordBreak(String s, Set<String> wordDict) {
int n = s.length();
boolean[] memo = new boolean[n + 1];
for(int i = 0; i <= n; ++i) memo[i] = true;
return dfs(memo, s, wordDict, 0, n);
}
public boolean dfs(boolean[] memo, String s, Set<String> dict, int start, int n) {
if (memo[start] == false) return false;
if(start == n) return true;
for(int i = start + 1; i <= n; ++i) {
if(dict.contains(s.substring(start, i)) &&
dfs(memo, s, dict, i, n))
return true;
}
memo[start] = false;
return false;
}
```