1
$\begingroup$

Given a set of $N$ distinct elements, it is well known that there is $2^N$ different subsets.

There is any way to accurately calculate the number of which those subsets holds exactly the same sum? i.e:

give the set {40,10,30,80,20,20} there are more than 4 subsets having the same sum:

  • 40+10+30 = 80
  • 40+20+20 = 80
  • 40+40 = 80
  • 80 = 80
  • ...

I'm not interested on know the final sums, just if there is a straight way to calculate the potential count of different sum values in all subsets.

| cite | improve this question | | | | |
$\endgroup$
  • 1
    $\begingroup$ It’s highly dependent on the specific set. If the members of the set are distinct powers of $2$, every subset gives a different sum. If they are $N$ consecutive integers, there’s a lot of collapsing. $\endgroup$ – Brian M. Scott Sep 5 '16 at 20:07
  • $\begingroup$ @BrianM.Scott I'm just thinking worst case scenario/upper bound, I completely understand that it is highly dependent on the set values. $\endgroup$ – Jesus Salas Sep 5 '16 at 20:19
  • 1
    $\begingroup$ It’s possible to get $2^N$ different sums; all that’s needed for this is that each member of the set be larger than the sum of the smaller members. The minimal examples are sets of powers of $2$, e.g., $\{1,2,4,8\}$, whose $2^4$ sums are the integers $0,1,\ldots,15$. $\endgroup$ – Brian M. Scott Sep 5 '16 at 20:26
  • $\begingroup$ @BrianM.Scott I feel like if you compute the subsets you will find yourself in trouble because is not possible to get $2^N$ different sums even following the approach you described. $\endgroup$ – Jesus Salas Sep 5 '16 at 21:02
  • 2
    $\begingroup$ It certainly is. Write out the $16$ subsets of $\{1,2,4,8\}$, and take their sums; you’ll get the integers $0$ through $15$. Basically you’re just looking at the binary representations of those $16$ integers. E.g., binary $1101$ corresponds to the sum $8+4+1=13$, while $0110$ corresponds to the sum $4+2=6$. $\endgroup$ – Brian M. Scott Sep 5 '16 at 21:09
1
$\begingroup$

The example suggests you are concerned with forming sums, possibly with repeated summands, by drawing from a multiset of positive integers. In this respect you are asking about the size of the feasible set of an integer programming problem, which is (without other assumptions) NP-hard.

This is an interesting problem, one that has been discussed previously at MathOverflow and at StackOverflow (but not on Math.SE as far as I could tell).

Let me offer an argument why we should not expect a straightforward useful formula for these counts, at least not one that can be evaluated in polynomial time. Let us restrict attention for the moment to sets of $N$ distinct values (no repetitions, so a strict set and not a multiset is involved).

If there were a "simple" (polynomial time in size of inputs) way to determine how many subset-sums occur, then we would certainly know, by comparing with the maximum possible value $2^N$, whether two distinct subsets give the same sum. This is a decision problem introduced by Woeginger and Yu (1992) in "On the equal-subset-sum problem", which they showed to be NP-complete. Therefore no formula evaluable in polynomial time is possible, unless P=NP. [A more recent paper by Cieliebak et al (2008) summarizes the complexity of several variants of equal-subset-sum, and moreover it is not behind a "paywall".]

Below I sketch an algorithm more sophisticated than simple "brute force" consideration of all possible $2^N$ (multi)subsets. I will then add an example and compare my suggestion to the interesting dynamic programming approach sketched in an answer to the StackOverflow post linked above.

One way to count the possible sums is to construct them all systematically by how many summands are used (counting the allowed repetitions afforded by the multiset). That is, the empty subset gives a zero sum. The single summand sums are precisely the distinct elements of the multiset. The distinct sums do not vary with the order of the summands, so we can systematically construct the distinct sums of $n$ summmands by extracting the distinct $n$-multisubsets of the given multiset in (say) lexicographic order.

An algorithm for doing so was described in this recent Answer.

It is then necessary to redact those $n$-summand sums which agree with results obtained by the same or fewer number of summands, and merge those which are novel. We will eliminate duplicates most efficiently if we maintain the list of sums achieved in order. While (as you note) lexicographic generation does not always produce new sums in ascending order, it does tend to produce long runs of ascending order.

The "dynamic programming approach" sketched in the SO Answer alluded to above proceeds instead by recursively including the available elements from smallest to largest. We only need bits up to the sum of all elements to record which of these respective sums are achieved or not. This is a pseudo-polynomial time (and space) algorithm.

Example (to do)

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Thanks @hardmath for your answer, however I'm not asking about a potential algorithm to solve the problem, I can do that by brute force with O(N^2), yet exponential but working one. Also, I do not see how lexicographic order in this case provide any improvement to sort out the count of different sum, applying an algorithm, as you pointed out very well is is NP-Hard and thus not computable in a reasonable amount of time, my question is asking for the straight way, what I expect is a formula, not an algorithm. $\endgroup$ – Jesus Salas Sep 6 '16 at 0:02
  • $\begingroup$ I misspoke in described the decision problem for Subset Sum as NP-hard, when it is actually NP-complete (a different notion). If there were a known formula to count the number of different sums possible, I would gladly share it. Instead I'm sketching an approach less naive than the "brute force" $O(2^N)$ algorithm inspecting all "subsets". The reason for the lexicographic ordering is to produce long runs of increasing sums and therefore cut down on the cost of merging the new sums of $n$ summands with the list of previous sums (using less than $n$ sumands). $\endgroup$ – hardmath Sep 6 '16 at 13:34
  • $\begingroup$ I'm still trying to see how a lexicographic ordering could help with this as this ordering schema do not really provide an increasing sums for the sets. Either way if you know for sure there is no formula to compute straight the number of different sums modify your answer to say this and then suggest other approaches and justify the lexicographic order and I'll be gladly to accept it as an answer. $\endgroup$ – Jesus Salas Sep 6 '16 at 16:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.