Subset Sum problem (w/ limited scope)

This question isn't actually a fortran question. However, there
might be a fortran person here with some insights?

The "Subset Sum" problem (stated various ways depending on what you
are reading):

Given: a set of integers, some may be positive, some negative.
Find: a subset of those integers that sums up to zero.

In this basic problem, the subset size can itself be quite large.
There is no "fantastic" way to solve this problem for a large set of
integers. The total number of possible subsets is 2**n, where n is
the number of integers in the original set.

What I want to do:
Limit the maximum number of integers that can be included in the
subset that must add up to zero ( say 6 integers maximum ). Limiting
the maximum subset size to 6 does greatly reduce the memory and
computations required to solve this problem. However, as the
original set size grows to n=100 and above, even limiting the max.
subset size to 6 starts requiring huge amounts of memory.

Does anyone have any information or insights or know of any web
references that they can point me to that may be of help?

Thanks,
Dan
.

Quantcast