The problem statement is, You are given a string and an array of some words. All the words are substring of the given string. You have to find all the ways to construct the string from the words of the array.

Suppose you are given a string "abcdef" and an array={ab,abc,cd,def,abcd}; here only one way to construct the string is ="abc+def"

my code prints all the ways. But it is really inefficient. it prints the same path multiple times if exists. It visits all the nodes. I want suggestions to memoize it so that it doesn't visit the same path if it visited it before. Can someone help me? here is my code:

bool constructstring(string target,vectorv) { if(target.size()==0){ for(int i=0;i<vec.size();i++)cout<<vec[i]<<" "; //prints the construction way cout<<endl; vec.pop_back(); return true; } for(int i=0;i<v.size();i++){ int found=target.find(v[i]); //finds the word is present in the string or not. if(found==0){ // checks the word is at the beginning of the string or not string s; s=target; s.erase(0,v[i].size()); vec.push_back(v[i]); constructstring(s,v); } } vec.pop_back(); return false; }