How to find sum of list subsets with a recursive function Python

Question

I need to write a recursive function to return sums of all possible subsets. I wrote the following code:

def subsets_sums(lst):
    if len(lst) == 0:
        return 0
    else:
        sum_list = [sum(lst)]
        for i in range(len(lst)):
            index_list = lst.copy()
            del index_list[i]
            test_list = subsets_sums(index_list)
            sum_list = test_list, sum_list
        return sum_list

But the output is very inelegant due to all the lists concatenations. something like:

(((0, [10]), ((0, [3]), [13])), (((0, [10]), ((0, [6]), [16])), (((0, [3]), ((0, [6]), [9])), [19])))

for the list:

[10,3,6]

How can I make it appear in a list like:

[0,10,0,3,13,0,10,0,6,16,0,3,0,6,9,19]

Can I change something within the code?

Why does your output contain duplicates? The possible sums are 0, 10, 3, 6, 13, 16, 9, and 19. — kaya3
– kaya3, Commented Dec 13, 2019 at 13:20

kaya3 · Accepted Answer · 2019-12-13 13:24:52Z

3

The possible sums of nums are:

nums[0] + s where s is a possible sum of nums[1:], i.e. those including the first number.
All the possible sums of nums[1:], i.e. those not including the first number.

The base case of the recursion is that the empty list has only 0 as a possible sum. We'll use sets to avoid duplicates in the output; a sum is either possible or it isn't.

def subset_sums(nums):
    if not nums:
        return {0}
    else:
        rest_sums = subset_sums(nums[1:])
        return { nums[0] + s for s in rest_sums } | rest_sums

Example:

>>> subset_sums([10, 3, 6])
{0, 3, 6, 9, 10, 13, 16, 19}

answered Dec 13, 2019 at 13:24

kaya3

51.6k7 gold badges87 silver badges118 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

גלעד ברקן Over a year ago

OP did not ask for "all possible sums," they asked for "sums of all possible subsets."

kaya3 Over a year ago

What do you think the difference is? Are you saying there is a subset of [10, 3, 6] whose sum is not included in this output, or are you saying there is a number in this output which is not the sum of a possible subset?

גלעד ברקן Over a year ago

OP provided this difference in the question description: "How can I make it appear in a list like: [0,10,0,3,13,0,10,0,6,16,0,3,0,6,9,19]"

גלעד ברקן Over a year ago

That's weird, though. That list seems to be too long. As far as I know, there are only 2^n possible subsets.

kaya3 Over a year ago

Yes, that list is too long, and doesn't make sense in the context of the question. 3 is not the sum of two different subsets. The OP's algorithm is incorrect, not just because of the output format.

|

kederrac · Accepted Answer · 2019-12-13 13:35:35Z

2

to get your desired output you can try:

lst = [10, 3, 6]
def subsets_sums(lst):
    if len(lst) == 0:
        return [0]
    else:
        sum_list = [sum(lst)]
        for i in range(len(lst)):
            index_list = lst.copy()
            del index_list[i]
            test_list = subsets_sums(index_list)
            sum_list = test_list + sum_list
        return sum_list
print(subsets_sums(lst))

output:

[0, 10, 0, 3, 13, 0, 10, 0, 6, 16, 0, 3, 0, 6, 9, 19]

answered Dec 13, 2019 at 13:35

kederrac

17.4k6 gold badges36 silver badges58 bronze badges

Comments

גלעד ברקן · Accepted Answer · 2019-12-14 16:27:08Z

0

Here's a method that shows us all the possible subsets together with their sum including the empty set. By using an index to iterate over A, we avoid copying the list each time if we were to use the sublist operator list[:].

def f(A, i=0):
  if i == len(A):
    return [([], 0)]

  rest = f(A, i + 1)

  return rest + [(s + [A[i]], _s + A[i]) for s, _s in rest]

print f([1, 2, 3])

Output:

[([], 0), ([3], 3), ([2], 2), ([3, 2], 5), ([1], 1), ([3, 1], 4), ([2, 1], 3), ([3, 2, 1], 6)]

answered Dec 14, 2019 at 16:27

גלעד ברקן

24k3 gold badges29 silver badges64 bronze badges

Collectives™ on Stack Overflow

How to find sum of list subsets with a recursive function Python

3 Answers 3

9 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

9 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related