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

I am currently learning dynamic programming. While writing the code of best sum memoization I am facing a problem.

Problem Statement:

"write a function bestsum(target sum, argument) that takes a target sum and an array of integers as argument. the function should return an array containing the shortest combination of the target sum. we can use an element of the array more than one."

example: input- 10 3 2 3 1

output-
             3 3 2 2

I tried to solve it. it works but takes a lot of time. How to solve it using dp memoization with c++???

*******my code link = https://github.com/Shuvro-d/Dynamic.Programming/blob/main/test%202.cpp