题目：

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

说明：

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

示例：

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

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

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

题目分析：

动态规划+回溯法DFS

代码：

class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        vector<string> result;
        string stc;
        vector<bool> able(s.size() + 1, false);
        vector<vector<string>> set(s.size() + 1, vector<string>());
        able[0] = true;
        for (size_t i = 1; i <= s.size(); ++i)
        {
            vector<string> temp;
            for (size_t j = 0; j<i; ++j)
            {
                if (able[j]==true&&contain(s, wordDict, temp, j, i - 1))
                {
                    able[i] = true;
                }
            }
            set[i] = temp;
        }
        int j = 0, k = set[s.size()].size();
        if (!able[s.size()])
            return result;
        word(s, stc, result, wordDict, able, set, s.size(), j);
        if (!result.empty())
        {
            for (size_t i = 0; i<result.size(); i++)
                result[i] = result[i].substr(0, result[i].size() - 1);
        }
        return result;
}

    bool word(string s, string& stc, vector<string>& result, vector<string>& wordDict, vector<bool>& able, vector<vector<string>>& set, int start, int j) {
        if (start == 0)
        {
            result.push_back(stc);
            return true;
        }
        if (start<0)
            return false;
        if (able[start])
        {
            int k = set[start].size();
            while (j<k)
            {
                stc = stc.insert(0," ").insert(0, set[start][j]);
                word(s, stc, result, wordDict, able, set, start - set[start][j].size(), 0);
                stc = stc.substr(set[start][j].size()+1);
                if (start == s.size()&&j>=k)
                    return false;
                ++j;
            }
            return false;
        }

        return false;
}

    bool contain(string s, vector<string>& wordDict, vector<string>& temp, int start, int end) {
        string t=s.substr(start,end-start+1);
        for(auto& word:wordDict)
            if(word==t)
                temp.push_back(word);
        if(temp.empty())
            return false;
        else
            return true;
    }
};