Re: counting subsets of S so that sum(S_n) = N

stdazi@xxxxxxxxx wrote:

Given the set of integers S = {e_1,e_2 , ... e_n } find (count) all
subsets S_n[...] that sum(S_n) = N, for a
given integer N.

The closely related problems of deciding /whether/ there is any subset
summing to the desired total, and of finding at least one such subset
if any exist at all, are NP-complete and NP-hard respectively -- which
means that they are in a class of problem that some very clever people
have spent years looking for efficient solutions to without finding any.

Your problem isn't /quite/ the same, but I (speaking as a non-expert)
very much doubt whether there is any efficient solution to that either.

Sometimes it's possible to find efficient partial solutions to NP-hard
problems -- ones that find approximate solutions, or which find
solutions quickly in many, but not all, cases. I don't know whether
there is any such "near-miss" available for this particular problem.

-- chris
.