class Solution {
public:
    unordered_map<string, vector<string>> memo;

    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);
    }


    vector<string> back(string s, unordered_map<string, int>& set) {
        if (memo[s].size() != 0) {
            return memo[s];
        }

        vector<string> result;
        //std::cout << "Having s = " << s << "\n";
        for (int i = 1; i <= s.length(); ++i) {
            string tmp = s.substr(0, i);
            if (set[tmp] != 0) {
                //std::cout << "Got : " << tmp << " trying: " << s.substr(i) << "\n";
                string rest = s.substr(i);
                if (rest != "") {
                    const auto& restResult = back(rest, set);
                    for (auto r : restResult) {
                        result.push_back(tmp + " " + r);
                    }
                } else {
                    result.push_back(tmp);
                }

            }
        }

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