Title Description
Given a non empty string s and a dictionary wordDict containing a list of non empty words, add spaces in the string to construct a sentence so that all the words in the sentence are in the dictionary. Return all these possible sentences.

explain:

• Words in the dictionary can be reused when separating.
• You can assume that there are no duplicate words in the dictionary.

Example 1:
Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
"cats and dog",
"cat sand dog"
]
Example 2:
Input:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output:
[
"pine apple pen apple",
"pineapple pen apple",
"pine applepen apple"
]
Explanation: note that you can reuse words in the dictionary.
Example 3:
Input:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
Output:
[]

Conventional thinking:
Similar to the problem of number arrangement, to get all the solutions, you need to save the leaf nodes, and the division method is similar to the number arrangement. If the encountered string is in the dictionary, add it, otherwise it will recurse. Because path passes a value, the backtracking process is not explicitly written out.

void dfs(s,u,now){//u is the beginning of the new word
    if(u==n) Record answer end;
    for(int j = u; j < n; j++){ //j is the cut-off position of the new word
        if(s[u~j]Exist in dictionary) dfs(s,j+1,now+s[u~j]+' ');      
    }
}

However, this solution will lead to timeout. For example

s="aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
wordDict = ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]

Because there are a lot of repeated calculations, after calculating dfs(1), you have to calculate dfs(2)... The two methods are as follows: you need to know the dynamic programming formula in advance, but the meaning is different.
1) You need to know in advance whether the string after j can be spelled out by the dictionary if u~j can be composed of words in the dictionary, so as to reduce repeated calculation. Reference link
2) You can know in advance that the words between u ~ j+1 are words in the dictionary. The words ending in f[j+1] with j+1 can be composed of words in the dictionary, so continue to recurse downward, otherwise it will not recurse.

This topic is an extension of topic 139.

• Save the dynamic programming formula of 139 questions, f[i] indicates whether the string ending in I can be composed of words in the dictionary.
• Add some judgment conditions on the basis of conventional ideas. If the conditions are met, continue to recurse downward. There are two ways, so there are two different solving codes.

Method 2: f[i] indicates whether the word ending with I can be composed of words in the dictionary.

class Solution {
public:
    vector<bool> f;
    unordered_set<string> hash;
    int n;
    vector<string> ans;
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        n = s.size();
        for(auto w:wordDict) hash.insert(w);
        f.resize(n+1);
        f[0]=true;
        for(int i=1;i<=n;i++)
        {
            for(auto w:wordDict)
            {
                int num=w.size();
                if(i-num>=0 && s.substr(i-num,num)==w)
                {
                    f[i]=f[i] ||f[i-num];
                }
            }
        }
        dfs(s,0,"");
        return ans;
    }
    void dfs(string s,int u,string path)
    {
        if(u==s.size())
        {
            path.pop_back();
            ans.push_back(path);
            return;
        }
        for(int i=u;i<n;i++)
        {
            if (hash.count(s.substr(u, i - u + 1)) && f[i + 1])
                dfs(s,i+1,path+s.substr(u,i-u+1)+" ");
        }
    }
};

Method 1: f[i] means that i ~ n can be composed of words in the dictionary

class Solution {
public:
    vector<bool> f;
    unordered_set<string> hash;
    int n;
    vector<string> ans;
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        n = s.size();
        for(auto w:wordDict) hash.insert(w);
        f.resize(n+1);
        f[n] = true;
        for (int i = n - 1; ~i; i -- )
            for (int j = i; j < n; j ++ )
                if (hash.count(s.substr(i, j - i + 1)) && f[j + 1])
                    f[i] = true;
        dfs(s,0,"");
        return ans;
    }
    void dfs(string s,int u,string path)
    {
        if(u==s.size())
        {
            path.pop_back();
            ans.push_back(path);
            return;
        }
        for(int i=u;i<n;i++)
        {
            if (hash.count(s.substr(u, i - u + 1)) && f[i + 1])
                dfs(s,i+1,path+s.substr(u,i-u+1)+" ");
        }
    }
};