题目：

思考：

1. 本质上和单词拆分1没什么区别
2. 单词拆分1是问能不能拆
3. 单词拆分2是问把所有拆的方案列出来
4. 要列出所有方案，采用字典树+回溯

实现：

class Node
{
public:vector<Node*> check;bool isEnd;Node(int num){for (int i=0;i<num;i++){check.push_back(nullptr);}isEnd=false;}
};class Solution {
public:void dfs(string s,int start,string& current,vector<string>& ret,Node* root){if (start==s.size()){ret.push_back(current);return;}for (int end=start+1;end<=s.size();end++){string tempS=s.substr(start,end-start);if (searchTree(tempS,root)){if (current==""){current.insert(current.end(),tempS.begin(),tempS.end());}else{current+=" ";current+=tempS;tempS+=" ";}dfs(s,end,current,ret,root);for (int i=0;i<tempS.size();i++){current.pop_back();}}}}vector<string> wordBreak(string s, vector<string>& wordDict) {vector<string> ret;int size_word=wordDict.size();Node* root=new Node(26);for (auto word:wordDict){insertTree(word,root);}int n = s.size();string current="";dfs(s,0,current,ret,root);return ret;}void insertTree(string word,Node* root){Node* node=root;for (auto c:word){int index=c-'a';if (!node->check[index]){node->check[index]=new Node(26);}node=node->check[index];}node->isEnd=true;}bool searchTree(string word, Node* root) {Node* node = root;for (char c : word) {int index = c - 'a';if (!node->check[index]) {return false;}node = node->check[index];}return node->isEnd;}
};