题意理解

把一个字符串s拆分为若干个子串，要求每个子串都是数组dic中的某个元素。拆分的方***有多种，要求输出所有的方法，每一种拆分方法用空格将子串隔开从而形成一个字符串。

方法一

深度优先搜索
看到题目要求的数据较小，考虑使用深度优先搜索枚举所有的可能性。如果s可以被正确拆分，说明其头部的一段子串是dic中的元素。

每次搜索时，遍历dic数组。对于其中的每个元素，判断它和s的头部等长的子串是否相同。
1、如果相同：把s头部对应的子串剔除，拆分剩余的部分remain，进入递归；
2、如果不同，判断dic中下一个元素。
边界条件：s为空，说明s被拆分完毕。

由于dic中可能出现重复的元素，会导致最后得到的拆分种类重复，需要先将dic中重复的元素剔除。但是dic中的一个元素可以重复利用。这两点不矛盾。

以"nowcoder",["now","oder","coder"]为例，过程如下：

具体代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param dic string字符串vector 
     * @return string字符串vector
     */
    vector<string> ans;
    void dfs(vector<string>& dic, string remain, string ss)
    {
        if (remain=="")
        {
            //删除最后一个空格
            ss.pop_back();
            ans.push_back(ss);
            return;
        }
        //遍历dic数组中每个元素
        for (int i=0;i<dic.size();i++)
        {
            string sub_str = remain.substr(0,dic[i].size());
            //匹配成功
            if (sub_str == dic[i])
            {
                //在传参时进行remain和ss的更新
                dfs(dic, remain.substr(dic[i].size(),remain.size()-dic[i].size()), ss+sub_str+" ");
            }
        }
        return;
    }
    
    vector<string> wordDiv(string s, vector<string>& dic) {
        // write code here
        unordered_map<string, bool> repeat;
        for (int i=0;i<dic.size();i++)
        {
            if (repeat[dic[i]]) {dic.erase(dic.begin()+i); i--;}
            else repeat[dic[i]] = true;
        }
        dfs(dic, s, "");
        return ans;
    }
};

时间复杂度： $O(N^N)O(N^N)$。最坏的情况，每次只匹配s中的第0个字符，每次匹配需要遍历一遍dic。s和dic的长度均为N。
空间复杂度： $O(N)O(N)$。递归的深度最多和s一样长，开辟的新空间repeat、ss等长度至多为N。

方法二

动态规划
使用二维数组ans记录，s[0~i]可以被拆分的所有方法，即ans的每个元素对应s[0~i]拆分的答案（元素类型为string的一维数组）。

要求ans[i]，此时ans[0]~ans[i-1]均已知。如果s[j~i]是dic中的元素，则ans[i]的拆分方法里要包含ans[j-1]+" "+s[j~i]，这里j可以从0取到i。当j为0时，直接将s[0~i]做为ans[i]的一种拆分方法即可。

状态转移方程为，这里的求和符号对应数组push_back操作：
$ans[i]={\sum }_{j=1}^i{\sum }_{k=0}^{\mathrm{\mid }ans[j-1]\mathrm{\mid }}(ans[j-1][k]+s[i\mathrm{.}\mathrm{.}\mathrm{.}j])ans[i]\; =\; \backslash sum\_\{j=1\}^i\backslash sum\_\{k=0\}^\{|ans[j-1]|\}\; (ans[j-1][k]+s[i...j])$

以为"nowcoder",["now","no","coder","w"]例，ans结果如图所示：

具体代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param dic string字符串vector 
     * @return string字符串vector
     */
    
    vector<string> wordDiv(string s, vector<string>& dic) {
        // write code here
        //dictionary记录dic中有哪些元素
        unordered_map<string, bool> dictionary;
        //ans[i]表示s[0]~s[i]拆分的所有情况
        vector<vector<string>> ans(s.size());
        for (int i=0;i<dic.size();i++)
        {
            dictionary[dic[i]] = true;
        }
        for (int i=0;i<s.size();i++)
        {
            for (int j=0;j<=i;j++)
            {
                if (dictionary[s.substr(j,i-j+1)])
                {
                    //j==0时要特殊处理
                    if (!j) ans[i].push_back(s.substr(j,i-j+1));
                    else
                    {
                        for (int k=0;k<ans[j-1].size();k++)
                        {
                            //当前拆分方法如何得到
                            ans[i].push_back(ans[j-1][k] + " " + s.substr(j,i-j+1));
                        }
                    }
                }
            }
        }
        return ans[s.size()-1];
    }
};

时间复杂度： $O(N^2\ast 2^N)O(N^2*2^N)$。外面是双重循环，每个循环的长度为N；最内侧的第三重循环遍历的是之前拆分的种数，对于长度为N的字符串来讲最多有$2^{N}2^N$种。
空间复杂度： $O(N\ast 2^N)O(N*2^N)$。ans有N行，每行最多可能包含了$2^{N}2^N$种拆分方法