word break

#include <bits/stdc++.h>
using namespace std;

int main() {
    int i,j,t,m,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        set<string>s;
        string str;
        for(i=0;i<n;i++){cin>>str; s.insert(str);}
        cin>>str;
        n=str.length();
        vector<bool> dp(s.size()+1,false);
        dp[0]=true;

        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(dp[j])
                {
                    string word = str.substr(j,i-j);
                    if(s.find(word)!= s.end())
                    {
                        dp[i]=true;
                        break;
                    }
                }
            }
        }
        cout<<dp[n]<<endl;
    }
    return 0;
}


-------------------word break 2----
#include <bits/stdc++.h>
using namespace std;
set<string>ss;
unordered_map<string,int> mp;
void test(string s,int i,int n,string cur,string ans)
{
    cur+=s[i];
    if(i==n){
        if(mp.find(cur)!=mp.end()){
            ans+=cur;
            ss.insert(ans);
        }
        return;
    }
    if(mp.find(cur)!=mp.end())test(s,i+1,n,"",ans+cur+" ");
    test(s,i+1,n,cur,ans);
    return ;
}
int main() {
    int i,j,t,m,n;
    cin>>t;
    while(t--)
    {
        ss.clear();
        mp.clear();
        cin>>n;
        string str;
        for(i=0;i<n;i++){cin>>str; mp[str]++;}
        cin>>str;
        test(str,0,str.length()-1,"","");
        for(auto s:ss){
            cout<<"("<<s<<")";
        }
        cout<<endl;
    }
    return 0;
}