CODEWITHSUNDEEP
python-3.xalgorithm
Erel Segal-Halevi
Erel Segal-Halevi

Reputation: 36745

Enumerating all subsets with sum at most S

What is an efficient way to enumerate all subsets of a given list L of numbers, such that the sum of all numbers in the set is at most a constant S?

One option is to use the recipe for powerset from itertools, and then filter by the sum, like this:

for subset in powerset(L):
    if sum(subset) <= S:
        yield subset

But this may be very wasteful, since the number of subsets may be very large, and only a small number of them have a sum of at most S. What is a more efficient way to do this?

Upvotes: 0

Views: 70

Answers (1)

MBo
MBo

Reputation: 80187

You can generate all subsets with sums <= S but note that storing them might require a lot of space. For "dense" subset sum distribution we can use a list, where A[k] keeps list of subsets with sum k. For sparse sums it would be better to use dictionary where dict[key] keeps list of subsets with sum key (remember copy of dictionary for every x, update dictionary adding x to existing subsets from that copy)

L = [1,3,5,8,11,17, 19, 23]
S = 15
A = [[] for _ in range(S+1)]
A[0] = [[0]]  #fake item to make non-zero list
for x in L:
    for ss in range(S, x-1,-1):
        l = len(A[ss-x])
        if len(A[ss-x]):
            for Y in A[ss-x]:
                A[ss].append(Y + [x])
for a in A:
    for b in a:
        if len(b) > 1:
            print(b[1:], end = ',')
    print()
[1],

[3],
[1, 3],
[5],
[1, 5],

[3, 5],[8],
[1, 3, 5],[1, 8],

[3, 8],[11],
[1, 3, 8],[1, 11],
[5, 8],
[1, 5, 8],[3, 11],
[1, 3, 11],

Upvotes: 1

Related Questions