Word Break II [Leetcode]

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].
A solution is ["cats and dog", "cat sand dog"].

Solution: DP( for breaking input string s) + DFS(for generating the set of resulting strings, each of which is one possible break)

class Solution {
public:
    void DFS(vector<string>& ret, unordered_map<int, vector<int> >& hashmap, int cur, string s){
        if(cur==0){
            ret.push_back(s);
            return;
        }
        if(cur<s.size())
            s.insert(cur, " ");
        for(vector<int>::iterator it = hashmap[cur].begin(); it!=hashmap[cur].end(); ++it)
            DFS(ret, hashmap, *it, s);
    }
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        int n = s.size();
        vector<string> ret;
        if(n==0) return ret;
        int* wb = new int[n+1];
        memset(wb, 0, (n+1)*sizeof(int));
        wb[0] = 1;
        unordered_map<int, vector<int> > hashmap;
        for(int i=1; i<=n; ++i){
            for(unordered_set<string>::iterator it = dict.begin(); it!=dict.end(); ++it){
                string ele = *it;
                int length = ele.size();
                if(i-length>=0){
                    if(wb[i-length]==1 && s.substr(i-length, length).compare(ele)==0){
                        wb[i]=1;
                        hashmap[i].push_back(i-length);
                    }
                }
            }
        }
        if(wb[n]==0) return ret;
        DFS(ret, hashmap, n, s);
        return ret;
    }
};