Combinatorics or another approach? [closed]

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 11 years ago.

Improve this question

I've recently read this problem, first, I thought of a combinatorial approach, but it seems nobody - along the contestants - has submitted such a solution. Is a solution using combinatorics possible? If not, what's the solution? The problem briefly is: Given a dictionary of M words, where any two words can be joined together and possibly 开发者_JAVA技巧overlapping some letters with each other, find how many strings of length N can be formed from the dictionary. The combinatorial approach has a downer limit of M!, then for each two consecutive words, you should try intersecting them. That's what I thought of. I doubt it'd work. Please help?

---

Don't confuse combinatorics with brute force. This is clearly a combinatorial counting problem but the time limit also rules out any brute force solution.

I think you can solve this with dinamic programming. For example, suppose our substring are "CAT and TCAT" and we need to cover a word of size 100

if we start with "CAT" we have 97 letters left if we start with "TCAT" we have 96 letters left.

So, if f(n) is the number of solutions for a matching of size n, we would have f(100) = f(97) + f(96).

Note, however, that this is clearly too simplified and not enough - you also need to cover the cases where the strings overlap and make sure that you don't count the same solution twice.

---

if you ignore the overlap, this is the subset sum problem. and considering the overlap, if you replace the overlapping combinations with their concatenations, you'll get a set of words that have no possiblity of overlap, and after that if you replace the strings with their lengths and then want to find sums that add up to N, that is exactly the subset sum problem.