class Solution
{
public:
    vector<string> wordBreak(string s, vector<string> &wordDict)
    {
        unordered_map<string, vector<string>> m;
        return helper(s, wordDict, m);
    }
    vector<string> helper(string s, vector<string> &wordDict, unordered_map<string, vector<string>> &m)
    {
        if (m.count(s))
            return m[s];
        if (s.empty())
            return {""};
        vector<string> ans;
        for (string word : wordDict)
        {
            if (word != s.substr(0, word.size()))
                continue;
            vector<string> res = helper(s.substr(word.size()), wordDict, m);
            for (string str : res)
            {
                ans.push_back(word + (str.empty() ? "" : " ") + str);
            }
        }
        return m[s] = ans;
    }
};