给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。

说明：

分隔时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

示例 1：

输入:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
输出:
[
  "cats and dog",
  "cat sand dog"
]
示例 2：

输入:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
输出:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
解释: 注意你可以重复使用字典中的单词。
示例 3：

输入:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
输出:
[]

题解
记忆化搜索+hash

class Solution {
public:
    string t;
    unordered_map<string,bool>mm;
    int Min,Max;
    vector<string> rem[10000];
    int max(int a,int b){
        return a > b ? a : b;
    }
    int min(int a,int b){
        return a < b ? a : b;
    }
    void dfs(int u,string &s){
        if(rem[u].size() != 0)return;
        if(u == s.size()){
            rem[u].push_back("");
            return;
        }
        for(int len = Min;len <= Max;len ++){
            if(s.size() - u >= len && mm.find(s.substr(u,len)) != mm.end()){
                dfs(u + len,s);
                for(auto &line : rem[u + len]){
                    rem[u].push_back(s.substr(u,len) + " " + line);
                }
            }
        }
    }
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        t = "";
        Min = 0x3f3f3f3f,Max = 0;
        for(int i = 0;i < wordDict.size();i ++){
            Min = min(wordDict[i].size(),Min);
            Max = max(wordDict[i].size(),Max);
        }
        for(auto &s : wordDict){
            mm[s] = true;
        }
        dfs(0,s);
        for(auto & s : rem[0]){
            s.erase(s.size() - 1,1);
        }
        return rem[0];
    }
};