1
class Solution {
2
  List<String> res = new ArrayList<>();
3
  String s;
4
  int index = 0;
5
  Set<String> set = new HashSet<>();
6

7
  public List<String> wordBreak(String s, List<String> wordDict) {
8
    this.s = s;
9
    for (String word : wordDict) set.add(word);
10
    backtrack("");
11
    return res;
12
  }
13

14
  public void backtrack(String sentence) {
15
    if (index == s.length()) {
16
      res.add(sentence.trim());
17
      return;
18
    }
19
    int indexCopy = index;
20
    for (int i = index + 1; i <= s.length(); i++) {
21
      String str = s.substring(index, i);
22
      if (set.contains(str)) {
23
        index = i;
24
        backtrack(sentence + " " + str);
25
        index = indexCopy;
26
      }
27
    }
28
    return;
29
  }
30
}