i have a list of numbers and a certain sum, and i need to calculate the possible number of ways to generate that sum

Question

Also, repetition of numbers is allowed.

I reffered to the program:

def subset_sum_recursive(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_recursive(remaining,target,partial + [n]) 

def subset_sum(numbers,target):
    #we need an intermediate function to start the recursion.
    #the recursion start with an empty list as partial solution.
    subset_sum_recursive(numbers,target,list())

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

but i am not getting where to put the count variable , its so confusing

Are you saying that your algorithm is also supposed to output `[3,3,3,3,3]`? — mgilson, Apr 16 '13 at 20:58
this is exactly your looking for : http://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a-given-sum — Moj, Apr 16 '13 at 20:59
@Moj, the code from the accepted answer is what this question is about — John La Rooy, Apr 16 '13 at 21:06

score 1 · Answer 1 · edited May 23 '17 at 12:12

It seems like you have a typical Counting Coins problem.

All the snippets you see there should solve the problem you want to solve (it also includes combinations that re-use the same number). I find convenient, if slow, this python version on that wiki:

def changes(amount, coins):
    ways = [0] * (amount + 1)
    ways[0] = 1
    for coin in coins:
        for j in xrange(coin, amount + 1):
            ways[j] += ways[j - coin]
    return ways[amount]

print changes(100, [1, 5, 10, 25])
print changes(100000, [1, 5, 10, 25, 50, 100])

If you want to know more, refer to this previous answer to a similar question - it breaks down the possible variants of the problem and exposes a pretty good solution.

score 0 · Answer 2 · edited May 23 '17 at 12:04

0

Not sure about canonical way to solve this problem, may be guru knows. But I find my solution quite nice:

import itertools
inp = [3,9,8,4,5,7,10]
outp = list()
target = 15
for x in range(2,len(inp)):
    outp.extend([ tsum for tsum in itertools.combinations(inp,x) if sum(tsum) == target ])
outp

UPD This is quite satisfactory for small inputs. For large inputs it doesn't scale very well. – @gnibbler Consider reading this question if you have large input

edited May 23 '17 at 12:04

Community

1
1

answered Apr 16 '13 at 21:30

singer

2,616
25
21

2

This is quite satisfactory for small inputs. For large inputs it doesn't scale very well. – John La Rooy Apr 16 '13 at 21:41

score 0 · Answer 3 · answered Apr 16 '13 at 21:41

you can also define a list in main and the append to list when ever one solution is found :

if s == target:
        print "sum(%s)=%s"%(partial,target)
        solutions.append("sum(%s)=%s"%(partial,target))

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

i have a list of numbers and a certain sum, and i need to calculate the possible number of ways to generate that sum

3 Answers3