Untitled

vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
    int n = s.size();
    if (n == 0)
        return {};
        
    // First: identify the break points (and that there exists at least one way to break it).
    // D[i] = True if it is possible to break up s[:i] in at least one way.
    vector<bool> D(n+1, false);
    D[0] = true;
    for (int i=1; i <= n; i++) {
        for (int j=i-1; j >= 0 && D[i] == false; j--) {
            D[i] = D[j] && wordDict.find(s.substr(j, i-j)) != wordDict.end();
        }
    }
    
    if (!D[n])  // There is no solution.
        return {};
        
    // Find the i such that D[i] is true.
    // In given example: break_points = [0,3,4,7,10].
    vector<int> break_points;
    for (int i=0; i < D.size(); i++) {
        if (D[i]) {
            break_points.push_back(i);
        }
    }
    
    int m = break_points.size();

    // Now find the solution based on the breakpoints.
    // E[i]: Set of all strings we can create using s[:break_points[i]].
    // In the example: E[0] = [""], E[1] = ["cat"], E[2] = ["cats"], E[3] = ["cats and", cat sand"]
    vector<vector<string>> E(m); 
    E[0] = {""};
    for (int i = 0; i < m; i++) {
        for (int j=i-1; j >=0; j--) {  // Will now compute E
            // t is the string defined from breakpoints i to j
            string t = s.substr(break_points[j], break_points[i] - break_points[j]);  
            if (wordDict.find(t) != wordDict.end()) {
                for (auto& u : E[j]) 
                    E[i].push_back(u + " " + t);
            }
        }
    }
    
    // Need to chop off the extra " " at the start of each string in E[m-1]
    vector<string> R;
    transform(E[m-1].begin(), E[m-1].end(), back_inserter(R), [](string& s) {return s.substr(1,s.size()-1);});
    return R;
}