Accepted without dp


#1

vector ans;
string str;
void rec(string A,int l,unordered_set &m)
{
int n=A.size();
if(l==n){
str.pop_back();
ans.push_back(str);
}
string s;
for(int i=l;i<n;i++){
s.push_back(A[i]);
if(m.find(s)!=m.end())
{
string temp=str;
str+=s+" ";
rec(A,i+1,m);
str=temp;
}
}
}
vector Solution::wordBreak(string A, vector &B) {
unordered_set m;
ans.clear();
str.clear();
for(auto x:B)
m.insert(x);
rec(A,0,m);
return ans;
}