solution.md

# 单词拆分 II

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

<p><strong>说明：</strong></p>

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

<p><strong>示例 1：</strong></p>

<pre><strong>输入:
</strong>s = &quot;<code>catsanddog</code>&quot;
wordDict = <code>[&quot;cat&quot;, &quot;cats&quot;, &quot;and&quot;, &quot;sand&quot;, &quot;dog&quot;]</code>
<strong>输出:
</strong><code>[
&nbsp; &quot;cats and dog&quot;,
&nbsp; &quot;cat sand dog&quot;
]</code>
</pre>

<p><strong>示例 2：</strong></p>

<pre><strong>输入:
</strong>s = &quot;pineapplepenapple&quot;
wordDict = [&quot;apple&quot;, &quot;pen&quot;, &quot;applepen&quot;, &quot;pine&quot;, &quot;pineapple&quot;]
<strong>输出:
</strong>[
&nbsp; &quot;pine apple pen apple&quot;,
&nbsp; &quot;pineapple pen apple&quot;,
&nbsp; &quot;pine applepen apple&quot;
]
<strong>解释:</strong> 注意你可以重复使用字典中的单词。
</pre>

<p><strong>示例&nbsp;3：</strong></p>

<pre><strong>输入:
</strong>s = &quot;catsandog&quot;
wordDict = [&quot;cats&quot;, &quot;dog&quot;, &quot;sand&quot;, &quot;and&quot;, &quot;cat&quot;]
<strong>输出:
</strong>[]
</pre>


## template

```cpp
#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    vector<string> res;
    unordered_set<string> wordset;
    unordered_set<int> lenset;
    vector<string> wordBreak(string s, vector<string> &wordDict)
    {
        for (const auto &w : wordDict)
        {
            wordset.insert(w);
            lenset.insert(w.size());
        }
        vector<int> dp(s.size() + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= s.size(); ++i)
        {
            for (const auto &j : lenset)
            {
                if (i >= j && dp[i - j] && wordset.count(s.substr(i - j, j)))
                    dp[i] = 1;
            }
        }

        if (dp.back() == 0)
            return res;
        backtrack(dp, 0, s, "");
        return res;
    }

    void backtrack(vector<int> &dp, int idx, string &s, string tmp)
    {
        if (idx == s.size())
        {
            tmp.pop_back();
            res.push_back(tmp);
            return;
        }

        for (int i = idx + 1; i < dp.size(); ++i)
        {
            if (dp[i] == 1 && wordset.count(s.substr(idx, i - idx)))
            {
                backtrack(dp, i, s, tmp + s.substr(idx, i - idx) + " ");
            }
        }
    }
};

```

## 答案

```cpp

```

## 选项

### A

```cpp

```

### B

```cpp

```

### C

```cpp

```