CODEWITHSUNDEEP
pythonalgorithmlistrecursion
DanBoguslavsky
DanBoguslavsky

Reputation: 117

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

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?

Upvotes: 4

Views: 528

Answers (3)

גלעד ברקן
גלעד ברקן

Reputation: 23955

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)]

Upvotes: 0

kederrac
kederrac

Reputation: 17322

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]

Upvotes: 2

kaya3
kaya3

Reputation: 51053

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}

Upvotes: 3

Related Questions