class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        unordered_map<string, int> set;
        unordered_map<string, vector<string>> memo;
        for (const auto& word : wordDict) {
            set[word]++;
        }
        return back(s, set, memo);
    }


    vector<string> back(const string& s, unordered_map<string, int>& set, unordered_map<string, vector<string>> memo) {
        if (memo[s]) {
            return memo[s];
        }

        vector<string>> result;
        //std::cout << "Having idx = " << idx << "\n";
        for (int i = 1; i <= s.length(); ++i) {
            string tmp = s.substr(0, i);
            if (set[tmp] != 0) {

                if (sentence.size() == 0) {
                    sentence += str;
                } else {
                    sentence += " " + str;
                }
                auto restResult = back(s.substr(i+1), set, memo);
                for (auto r : restResult) {
                    result.push_back(tmp + " " + r);
                }

            }
        }

        memo[s] = result;
        return result;
    }
};