fork download 
  1. def subset_sum_recursive(numbers,target,partial):
  2.     s = sum(partial)
  3.  
  4.     #check if the partial sum is equals to target
  5.     if s == target:
  6. 	if 9 in partial:
  7. 	    if 18 in partial:
  8. 		if len(partial) == 6:
  9.             	    print "sum(%s)=%s"%(partial,target)
  10.     if s >= target:
  11.         return # if we reach the number why bother to continue
  12.  
  13.     for i in range(len(numbers)):
  14.         n = numbers[i]
  15.         remaining = numbers[i+1:]
  16.         subset_sum_recursive(remaining,target,partial + [n]) 
  17.  
  18. def subset_sum(numbers,target):
  19.     #we need an intermediate function to start the recursion.
  20.     #the recursion start with an empty list as partial solution.
  21.     subset_sum_recursive(numbers,target,list())
  22.  
  23. if __name__ == "__main__":
  24.     subset_sum([2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,18],72)
Success #stdin #stdout 0.09s 4676KB
comments (?)
stdin 
Standard input is empty
stdout 
sum([2, 9, 12, 15, 16, 18])=72
sum([2, 9, 13, 14, 16, 18])=72
sum([3, 9, 11, 15, 16, 18])=72
sum([3, 9, 12, 14, 16, 18])=72
sum([3, 9, 13, 14, 15, 18])=72
sum([4, 9, 10, 15, 16, 18])=72
sum([4, 9, 11, 14, 16, 18])=72
sum([4, 9, 12, 13, 16, 18])=72
sum([4, 9, 12, 14, 15, 18])=72
sum([5, 9, 10, 14, 16, 18])=72
sum([5, 9, 11, 13, 16, 18])=72
sum([5, 9, 11, 14, 15, 18])=72
sum([5, 9, 12, 13, 15, 18])=72
sum([6, 8, 9, 15, 16, 18])=72
sum([6, 9, 10, 13, 16, 18])=72
sum([6, 9, 10, 14, 15, 18])=72
sum([6, 9, 11, 12, 16, 18])=72
sum([6, 9, 11, 13, 15, 18])=72
sum([6, 9, 12, 13, 14, 18])=72
sum([7, 8, 9, 14, 16, 18])=72
sum([7, 9, 10, 12, 16, 18])=72
sum([7, 9, 10, 13, 15, 18])=72
sum([7, 9, 11, 12, 15, 18])=72
sum([7, 9, 11, 13, 14, 18])=72
sum([8, 9, 10, 11, 16, 18])=72
sum([8, 9, 10, 12, 15, 18])=72
sum([8, 9, 10, 13, 14, 18])=72
sum([8, 9, 11, 12, 14, 18])=72
https://ideone.com/VpDmL
language:
Python (cpython 2.7.16)
created:
14 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!