listsubset-sum

how can i divide a list as subsets which are sum upto given number(non repeat)?


from given list of numbers

nums=[4,3,2,3,5,2,1]

from itertools import combinations
nums=[4,3,2,3,5,2,1]
li=[]
for i in range(1,len(nums)):
    comb=combinations(nums,i)
    for j in comb:
        if sum(j)==5:
            li.append(j)

print(li)

and output is

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

I am able to find the subsets but the elements seem to be repeated so interested in non-repeating elements

I want the list of subsets that gives sum equal to 5 (without repetition)

example: [(5), (1, 4), (2,3), (2,3)]


Solution

  • If you change the loop slightly so that used numbers are removed from the list, they aren't reused in another sum, e. g.

    i = 1
    while i <= len(nums):
        comb = combinations(nums, i)
        for j in comb:
            if sum(j) == 5:
                li.append(j)
                for n in j: nums.remove(n)
                break
        else: i += 1    # increment only if nothing found