题目：
难度：Hard
相关话题：动态规划、回溯算法
给定一个非空 字符串 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"]
输出:[]
/**
* @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
* @param {string} s
* @param {string[]} wordDict
* @return {string[]}
*/
var wordBreak = function(s, wordDict) {
if(wordDict.length===0)return []
let mem={}
return dfs(s)
function dfs(s){
if (mem[s])
return mem[s]
let res = []
if (s.length == 0) {
res.push("");
return res;
}
for (let word of wordDict) {
if (s.startsWith(word)) {
let sublist = dfs(s.substring(word.length));
// console.log(sublist)
for (let sub of sublist) {
// console.log(sub)
res.push(word + (sub===""?"": " ") + sub)
}
}
}
mem[s]=res
return res;
}
};