Algorithm to reconstruct sentence from shuffled string Given a dictionary of words, and given a string which is an anagram of concatenation of group of words from the dictionary, is there an efficient algorithm to find valid set of  words that can form this string ?

eg1: dict = [ 'dog', 'cat', 'cow' ]
s = 'ocdgatcta'
ans = [ 'cat', 'cat', 'dog' ]


If we join the words in the answer to form the string, we can see that it is an anagram of the input string s

eg2: dict = [ 'dog', 'act', 'cat', 'cow' ]
s = 'ocdgatcta'
ans = [ 'cat', 'cat', 'dog' ] or [ 'act', 'cat', 'dog' ] or [ 'act', 'act', 'dog' ]


In the above case any of the above list is valid as the string formed by them is an anagram of the input string s

We can brute force but there seems to be overlapping sub problems. Can this be solved in polynomial time ?
This is NP-hard, so it's very unlikely there's a polynomial-time solution.  To see this, notice that any instance of the NP-hard problem Exact Cover can easily be encoded as an instance of your problem in such a way that there is a solution to this encoded instance if and only if there is a solution to the original Exact Cover instance.