-2

I have a list of numbers, say, [2,4,5,6,7].

I want to list all of the unique ways these numbers can be made into a sum, N, with repeats.

For example, if N were 8. Answers would be:

2+2+2+2
4+4
6+2
4+2+2

Order does not matter.

The closest I've got is the answer to this question: Finding all possible combinations of numbers to reach a given sum

def subset_sum(numbers, target, partial=[]): s = sum(partial)

# check if the partial sum is equals to target
if s == target: 
    print "sum(%s)=%s" % (partial, target)
if s >= target:
    return  # if we reach the number why bother to continue

for i in range(len(numbers)):
    n = numbers[i]
    remaining = numbers[i+1:]
    subset_sum(remaining, target, partial + [n]) 


if __name__ == "__main__":
    subset_sum([3,9,8,4,5,7,10],15)

#Outputs:
#sum([3, 8, 4])=15
#sum([3, 5, 7])=15
#sum([8, 7])=15
#sum([5, 10])=15

How could I modify this to allow for repeats?

Mr. A
  • 219
  • 4
  • 11
  • 2
    Let's see your code attempt – Miket25 Sep 03 '17 at 21:47
  • I guess `4+2+2` should also be a solution? – Tim Pietzcker Sep 03 '17 at 21:49
  • You need a combinaison of 2 numbers in a collection of 5. It's math, no Python. – Laurent LAPORTE Sep 03 '17 at 21:50
  • This question falls really under algorithms. A DP solution will suffice. – Miket25 Sep 03 '17 at 21:50
  • 1
    Take a look at solutions for the [Change-making problem](https://en.wikipedia.org/wiki/Change-making_problem). It’s very similar and solutions will likely give you an idea how to approach your problem. – poke Sep 03 '17 at 21:54
  • I have made a couple of attempts, but they're trash. The closest I got was the answer to a similar question, here. https://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a-given-sum – Mr. A Sep 03 '17 at 21:58
  • 4+2+2 is a solution – Mr. A Sep 03 '17 at 21:59
  • Yes, that linked question looks good to me. There is a one-line change in the accepted Python answer there that makes this work for repetitions. If you are having trouble with that, please clarify your question to explain *what exactly* you are having trouble with. – poke Sep 03 '17 at 22:10

1 Answers1

-1

You can try this:

import itertools

data = [itertools.product([2,4,5,6,7], repeat = i) for i in range(2, 5)]

new_data = [[b for b in i if sum(b) == 8] for i in data]

print(len(list(itertools.chain.from_iterable(new_data))))
Ajax1234
  • 69,937
  • 8
  • 61
  • 102