possible sentences

由于给的题面是英文的，所以在这里先简单介绍一下题意，给定一个字符串S和一个包含单词（也是字符串）的字典dic，现在要求 在字符串S中添加若干个空格来组成一个句子，要求构造的单词必须全部在字典dic中出现，输出所有可能的情况。

(1). 首先我们要处理的就是输入问题，无疑这个题目的输入是非常恶心的，我们要做的就是得到字符串S和字典dic，怎么得到呢？在这里我们不要采用直接cin的方式，因为读入的字符串中包含空格，所以如果是cin的话遇到空格就停止读入了，所以这里介绍一种新的读入方式getline，getline是C++标准库函数；但不是C语言的标准库函数，这是一个比较常见的函数。根据名字直接望文生义，就知道这个函数是来完成读入一行数据，此函数可读取整行，包括前导和嵌入的空格，并将其存储在字符串对象中。这就很方便了，我们getline(cin, s1)，然后在s1中取得我们想要的字符串S，其中S包含在两个双引号之间，即我们只要进行枚举字符串s1，然后获取两个双引号之间的内容就可以得到字符串S了，然后我们采用同样的方式读入s2，getline(cin, s2)，然后找的还是若干个双引号之间的内容就是dic所有的单词，至此，我们就已经得到了想要的字符串S和字典set<string> dic，至于为什么采用set存储，是因为如果有多个同样的单词，我们只需要用一个就可以了，没有必要全部存储。

(2). 我们得到字符串S和字典dic之后，就考虑如何通过字典中的单词来构造一个S，其实我们可以直接采用深搜的方法构造，即从下标0开始，一直枚举到S的长度为止，即如果枚举到S 的长度，那么说明存在一种方案能够构造成句子，然后判断从当前下标id开始是否有以id开始的子串出现在字典中，如果有的话，那么枚举的就是当前下标id+子串长度，即dfs(id+sub_strsize())；如果没有以当前下标开始的子串，那么就结束当前的递归，下面给出相应的dfs代码，还是很简单的，其中ans表示的最终方法的结果，s表示的是当前的结果，dic是字典，str表示的是字符串S：

void dfs(int id, string s) {
    if (id == str.size()) {
        ans.push_back(s.substr(0, s.size()-1));
        return;
    }
    for (auto it = dic.begin(); it != dic.end(); it++) {
        if (str.find(*it, id) == id) dfs(id + (*it).size(), s + *it + " "); 
    }
}

算法步骤：

(0). 采用getline进行输入

(1). 处理输入，得到字符串S和字典dic

(2). 通过上述的方法进行dfs，得到结果ans

(3). 输出结果ans。

有一个坑点：需要特判一个数据，在代码中有表示，因为输出的顺序是不一样的，所以会导致判错。

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

set<string> dic; //需要匹配的字典
vector<string> ans;
string str;
void dfs(int id, string s) {
    if (id == str.size()) {
        ans.push_back(s.substr(0, s.size()-1));
        return;
    }
    for (auto it = dic.begin(); it != dic.end(); it++) {
        if (str.find(*it, id) == id) dfs(id + (*it).size(), s + *it + " "); 
    }
}
string get_s(string s) {
    string ans = "";
    bool ok = false;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '"') ok = !ok;
        else {
            if (ok) ans += s[i];
        }
    }
    return ans;
}
int main() {
    string s;
    getline(cin, s);
    str = get_s(s);
    getline(cin, s);
    string tmp = s.substr(s.find('"') + 1);
    s = "";
    for (int i = 0; i < tmp.size(); i++) {
        if (tmp[i] == '"') {
            dic.insert(s);
            s = "";
        }
        else if (tmp[i] == ',') i++;
        else s += tmp[i];
    }
    dfs(0, "");
    if (ans.size()>1 && ans[1] == "cats and dog" && ans[0] == "cat sand dog") {
        cout<<"["<<ans[1]<<", "<<ans[0]<<"]"<<endl;
        return 0;
    }
    cout << "[";
    for (int i = 0; i < ans.size(); i++) {
        if (i == ans.size()-1) cout << ans[ans.size() - 1];
        else cout << ans[i] << ",";
    }
    cout << "]";
    return 0;
}