Word Break II

class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        vector<string> res;
        if (!wordBreakPossible(s, dict)) return res;
        wordBreakRe(s, dict, 0, "", res);
        return res;
    }
   
    void wordBreakRe(const string &s, const unordered_set<string> &dict,
                     int start, string sentence, vector<string> &res) {
        if (start == s.size()) {
            res.push_back(sentence);
            return;
        }
        if (start != 0) sentence.push_back(' ');
        for (int i = start; i < s.size(); ++i) {
            string word = s.substr(start, i-start+1);
            if (dict.find(word) == dict.end())
                continue;
            wordBreakRe(s, dict, i+1, sentence + word, res);
        }
    }
   
    bool wordBreakPossible(const string &s, const unordered_set<string> &dict) {
        int N = s.size();
        bool canBreak[N+1];
        memset(canBreak, false, sizeof(canBreak));
        canBreak[0] = true;
        for (int i = 1; i <= N; ++i) {
            for (int j = i-1; j >= 0; --j) {
                if (canBreak[j] && dict.find(s.substr(j, i-j)) != dict.end()) {
                    canBreak[i] = true;
                    break;
                }
            }
        }
        return canBreak[N];
    }
};

//another flavor
class Solution {
public:
//From right to left, compute the start index such that the substring[start ,current] is in the dictionary. Then backtrace from the beginning.
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        vector<list<int>> mark(s.length(),list<int>());
        for(int stop=s.length();stop>=0;stop--){
            if(stop<s.length()&&mark[stop].empty()) continue;
            for(int start=stop-1;start>=0;start--){
                if(dict.count(s.substr(start,stop-start)))
                    mark[start].push_back(stop);
            }
           
        }
           
        vector<string> result;
        collect(mark,0,s,"",result);
        return result;
   
    }
    void collect(vector<list<int>>& mark, int ind, const string& s,
                string path, vector<string>& result){
        for(auto& stop:mark[ind]){
            string sub =s.substr(ind,stop-ind);
            string newpath=path+(ind==0?sub:" "+sub);
            if(stop==s.length()) result.push_back(newpath);
            else collect(mark,stop,s,newpath,result);
        }           
   
    }
};