Word Break - Part 2

 Word Break - Part 2

                            Word Break - Part 2

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 = "snakesandladder",
dict = ["snake", "snakes", "and", "sand", "ladder"].

A solution is ["snakes and ladder",
           "snake sand ladder"].

For each test case, print all possible strings in one line. Each string is enclosed in (). See Example.
If no string possible print "Empty" (without quotes).

#include <bits/stdc++.h>
using namespace std;
void findsol(int index,unordered_map<string,int> mp,string s,string curr,string ans)
{
    curr+=s[index];
    if(index==s.size()-1){
        if(mp[curr]==1)
        {
        ans+=curr;
        cout<<"("<<ans<<")";
        }
        return ;
    }


    if(mp[curr]==1)
      {
      findsol(index+1,mp,s,"",ans+curr+" ");
      }
    findsol(index+1,mp,s,curr,ans);
      return;
   
}

int main() {
    //code
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
      
        string s;
        unordered_map<string,int> mp;
      
        for(int i=0;i<n;++i)
        {
        cin>>s;
        mp[s]++;
        }
       
        cin>>s;
        int i=1,j=0;
      
        findsol(0,mp,s,"","");
        cout<<endl;
       
    }
    return 0;
}