class Solution {

 public:

     vector<string> wordBreak(string s, unordered_set<string> &dict)

     {

         // Note: The Solution object is instantiated only once and is reused by each test case.

         vector<string> result;

         if(dict.empty())

             return result;

         const int len = s.size();

         bool canBreak[len]; //canBreak[i] = true 表示s[0~i]是否能break

         memset(canBreak, , sizeof(bool)*len);

         bool **pre = new bool *[len];//如果s[k..i]是字典中的单词,则pre[i][k]=true

         for(int i = ; i < len; i++)

         {

             pre[i] = new bool[len];

             memset(pre[i],  , sizeof(bool)*len);

         }

         for(int i = ; i <= len; i++)

         {

             if(dictContain(dict, s.substr(, i)))

             {

                 canBreak[i-] = true;

                 pre[i-][] = true;

             }

             if(canBreak[i-] == true)

             {

                 for(int j = ; j <= len - i; j++)

                 {

                     if(dictContain(dict,s.substr(i, j)))

                     {

                         canBreak[j+i-] = true;

                         pre[j+i-][i] = true;

                     }

                 }

             }

         }

         //return false;

         vector<int> insertPos;

         getResult(s, pre, len, len-, insertPos, result);

         return result;

     }

     bool dictContain(unordered_set<string> &dict, string s)

     {

         unordered_set<string>::iterator ite = dict.find(s);

         if(ite != dict.end())

             return true;

         else return false;

     }

     //在字符串的某些位置插入空格，返回新字符串

     string insertBlank(string s,vector<int>pos)

     {

         string result = "";

         int base = ;

         for(int i = pos.size()-; i>=; i--)

         {

             if(pos[i] == )continue;//开始位置不用插入空格

             result += (s.substr(base, pos[i]-base) + " ");

             base = pos[i];

         }

         result += s.substr(base, s.length()-base);

         return result;

     }

     //从前驱路径中构造结果

     void getResult(string s, bool **pre, int len, int currentPos,

                    vector<int>insertPos,

                    vector<string> &result)

     {

         if(currentPos == -)

         {

             result.push_back(insertBlank(s,insertPos));

             //cout<<insertBlank(s,insertPos)<<endl;

             return;

         }

         for(int i = ; i < len; i++)

         {

             if(pre[currentPos][i] == true)

             {

                 insertPos.push_back(i);

                 getResult(s, pre, len, i-, insertPos, result);

                 insertPos.pop_back();

             }

         }

     }

 };