# C++ solution using dp and backtrace(8ms)

1. using dp to just like "work break".

2. backtrace with dp.

class Solution {

`````` vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
if(s.empty() || wordDict.empty()) return vector<string>();
int n = s.size();
vector<bool> dp(n+1, false);
dp[n] = true;

for(int i=n-1; i >= 0; --i)
for(int j=i+1; j <= n; ++j)
if(dp[j] && wordDict.find(s.substr(i, j-i)) != wordDict.end()) {
dp[i] = true;
break;
}
if(!dp[0]) return vector<string>();

vector<string> ret;
bt(s, 0, wordDict, dp, ret);
return ret;
}

void bt(string &s, int idx, unordered_set<string> &dict, vector<bool> &dp, vector<string> &ret) {
static string tmp;
if(idx == s.size()) {
ret.push_back(tmp);
return ;
}
for(int i=idx+1; i <= s.size(); ++i) {
string str(s, idx, i-idx);
if(dp[i] && dict.find(str) != dict.end()) {
if(idx != 0) tmp += " ";
tmp += str;
cout << tmp << endl;

bt(s, i, dict, dp, ret);

if(idx == 0) tmp.erase(tmp.size()-str.size());
else tmp.erase(tmp.size()-str.size()-1);
}
}
}
``````

};

• Why `tmp.erase(tmp.size()-str.size())`? Is the motivation of this to restore the value of `temp` to before recursion state? While this sentence would erase from 0 `pos` for `tmp.size()-str.size()` number of chars, which effectively makes `tmp` equals `str`. Could you kindly explain?

• That is for erasing a white space and the last word in tmp. And you misremember the funtion erase.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.