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: https://github.com/Shuvro-d/Dynamic.Programming/blob/main/test.cpp