Leetcode -- Word Break II

TLE because I didn't use dynamic programming

 class Solution {  
 public:  
   vector<string> wordBreak(string s, unordered_set<string> &dict) {  
    vector<string> breaks;  
     string output;  
     wordBreakHelper(s, 0, dict, output, breaks);  
     return breaks;  
   }  
   void wordBreakHelper(string s, int start, unordered_set<string>& dict, string& output, vector<string>& breaks) {  
     if(start >= s.length()) {  
       breaks.emplace_back(output.substr(1));  
       return;  
     }  
     for(int i = start; i < s.length(); ++i) {  
       string sub(s.substr(start, i - start + 1));  
       if(dict.count(sub) > 0) {  
         output +=" " + sub;  
         wordBreakHelper(s, i + 1, dict, output, breaks);  
         output = output.substr(0, output.length() - 1-sub.length());  
       }  
     }  
   }  
 };  

Cut some branches

 class Solution {  
 public:  
   vector<string> wordBreak(string s, unordered_set<string> &dict) {  
    vector<string> breaks;  
     string output;  
     vector<bool> possible(s.length() + 1, true);  
     wordBreakHelper(s, 0, dict, output, breaks, possible);  
     return breaks;  
   }  
   void wordBreakHelper(string s, int start, unordered_set<string>& dict, string& output, vector<string>& breaks, vector<bool>& possible) {  
     if(start >= s.length()) {  
       breaks.emplace_back(output.substr(1));  
       return;  
     }  
     for(int i = start; i < s.length(); ++i) {  
       string sub(s.substr(start, i - start + 1));  
       if(dict.count(sub) > 0 && possible[i + 1]) {  
         output +=" " + sub;  
         int beforeTheChange = breaks.size();  
         wordBreakHelper(s, i + 1, dict, output, breaks, possible);  
         if(beforeTheChange == breaks.size()) {  
           possible[i + 1] = false;  
         }  
         output = output.substr(0, output.length() - 1-sub.length());  
       }  
     }  
   }  
 };