word-break II

class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        vector<bool>f(s.length()+1,false);
        vector<vector<bool>>prev(s.length()+1,vector<bool>(s.length()));
        f[0]=true;
        for(int i=1;i<=s.length();i++)
        {
            for(int j=0;j<i;j++)
            {
                if(f[j]&&dict.find(s.substr(j,i-j))!=dict.end()){
                    f[i]=true;
                    prev[i][j]=true;
                }
            }
        }
        vector<string>path,result;
        dfs(s,prev,s.length(),path,result);
        return result;
    }
    void dfs(string &s,vector<vector<bool>>&prev,int cur,vector<string>&path,vector<string>&result)
    {
        if(cur==0)
        {
            string tmp;
            for(int i=0;i<path.size();i++)
            {
                tmp+=path[i];
                if(i!=path.size()-1)tmp+=" ";
                result.push_back(tmp);
            }
        }
        for(int i=0;i<s.size();i++)
        {
            if(prev[cur][i]){
                path.push_back(s.substr(i,cur-i));
                dfs(s,prev,i,path,result);
                path.pop_back();
            }
        }
    }
};