140. Word Break II

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        List<String> result = new ArrayList<>();
        dfs(s, wordDict, 0, new ArrayList<>(), result);
        return result;
    }
    private void dfs(String s, List<String> wordDict, int start, List<String> list, List<String> res) {
        if (start == s.length()) {
            res.add(String.join(" ", list));
            return;
        }
        for (String w : wordDict) {
            int len = w.length(); // 我覺得很難想的是這個, 用 w 的 len 去抓 string 來比較, 但這樣的確很高效...
            if (start + len > s.length()) {
                continue;
            }
            String cur = s.substring(start, start + len);
            if (!w.equals(cur)) {
                continue;
            }
            
            // 如果比對後是存在 wordDict 沒錯的話(滿足 prefix), 就加入 list
            list.add(w);
            dfs(s, wordDict, start + len, list, res); // next substring part
            list.remove(list.size()-1); // backtracking
        }
    }
}

backtracking 2

use each index for substring

```java
class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        List<String> res = new ArrayList<>();
        dfs(0, s, new HashSet<>(wordDict), new ArrayList<>(), res);
        return res;
    }
    private void dfs(int start, String s, Set<String> set, List<String> list, List<String> res) {
        if (start == s.length()) {
            res.add(String.join(" ", list));
            return;
        }
        for (int i = start; i < s.length(); i++) {
            String str = s.substring(start, i+1);
            if (set.contains(str)) {
                list.add(str);
                dfs(i+1, s, set, list, res);
                list.remove(list.size()-1);
            }
        }
    }
}
```