140 Word Break II

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: Backtracking and avoid unnecessary checking

class Solution {
public:
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        vector<string> res;
        if (s.size()<=0 || dict.size()<=0)
            return res;
        vector<string> solution;
        vector<bool> possible = vector<bool>(s.size()+1,true);
        help(s,dict,0,s.size()-1,possible,solution,res);
        
        return res;
    }
    void help(string s,unordered_set<string> &dict,int start,int end,vector<bool> &possible,vector<string>&solution,vector<string>&res)
    {
        if (start>end)
        {
            string str;
            for (int i=0;i<solution.size();i++)
            {
                str+=(solution[i]+' ');
            }
            str.pop_back();
            res.push_back(str);
            return;
        }
        for (int i=start;i<=end;i++)
        {
            string tmp = s.substr(start,i-start+1);
            if (dict.find(tmp)!=dict.end() && possible[i+1])
            {
                solution.push_back(tmp);
                int before = res.size();
                help(s,dict,i+1,end,possible,solution,res);
                if (res.size()==before)
                    possible[i+1]= false;
                solution.pop_back();
            }
        }
    }
};