The idea is to use a DP array vector<vector<string>> to remember word break result at each idx. Traverse from the head of the string to the end. And for each idx, iterate all possible word and add to previous idx result. As the code show:

```
class Solution {
public:
vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
vector<vector<string>> dp(s.size(), vector<string>(0));
int max_s = 0;
for (unordered_set<string>::iterator it = wordDict.begin(); it != wordDict.end(); it++) {
max_s = max(max_s, (int)(*it).size());
}
for (int i = 0; i < s.size(); i++) {
for (int j = i; j >= 0 && i - j + 1 <= max_s; j--) {
string cur_string = s.substr(j, i - j + 1);
if (wordDict.find(cur_string) != wordDict.end()) {
// found a string from idx j to i.
// Add the cur_string to each string in result we already
// got from dp[j-1]
if (j == 0) {
dp[i].push_back(cur_string);
} else if (dp[j-1].size() > 0){
for (int k = 0; k < dp[j-1].size(); k++) {
dp[i].push_back(dp[j-1][k] + " " + cur_string);
}
}
}
}
}
return dp.back();
}
};
```

Per my understanding, this solution didn't do any redundant work comaparing to recursion. However, this code get TLE consistently. Can anyone take a look and see if I missed anything here?

Thanks!!