1
class Solution {
2
 public:
3
  void helper(string s, unordered_set<string> &dict, int start, int index, string current,
4
              vector<string> &ans) {
5
    if (start == s.size()) {
6
      ans.push_back(current);
7
      return;
8
    }
9
    if (index == s.size()) return;
10

11
    string sub = s.substr(start, index - start + 1);
12

13
    if (dict.count(sub) > 0) {
14
      string recursion;
15
      if (current.size() == 0)
16
        recursion = sub;
17
      else
18
        recursion = current + " " + sub;
19
      helper(s, dict, index + 1, index + 1, recursion, ans);
20
    }
21
    helper(s, dict, start, index + 1, current, ans);
22
    return;
23
  }
24
  vector<string> wordBreak(string s, vector<string> &wordDict) {
25
    unordered_set<string> dict;
26
    for (int i = 0; i < wordDict.size(); i++) {
27
      dict.insert(wordDict[i]);
28
    }
29
    vector<string> ans;
30
    helper(s, dict, 0, 0, "", ans);
31
    return ans;
32
  }
33
};