(see filename)

Find all unique combinations in a list of numbers whose sum is X.py

#Algorithm taken from here (+ cleaned + simplified + commented):
#https://chinmaylokesh.wordpress.com/2011/03/08/algorithm-to-find-all-distinct-sums-using-numbers-from-a-list-that-add-up-to-a-specified-sum/

def tsum(currentIndex,total):
  if total==SUM :
    s = ""
    for i in xrange(0,L):
      if record[i]:
        s = s + str(NUMBERS[i]) + ", "
    print s[0:-2] #remove last comma from result
    return
  for i in xrange(currentIndex,L):
    if total+NUMBERS[i]>SUM : #Have we "blown through the roof" yet?
      continue #Abort!
    if i>0 and NUMBERS[i]==NUMBERS[i-1] and not record[i-1] : #In a streak of equal numbers, don't repeat evaluation for combinations already rejected. 
      continue
    record[i]=1 #Mark as viable member of a possible solution
    tsum(i+1,total+NUMBERS[i])
    record[i]=0 #Clear the mark (either we found a solution XOR this number has been rejected as not part of a possible solution)
 
#SUM = 4
#NUMBERS = [4, 3, 2, 2, 1, 1]
SUM=33250
NUMBERS = [176,290,59,383,281,200,5410,680,910,740,800,195,195,932,796,704,1160,235,326,326,326,1199,300,300,300,797697,18549,17204,14575,66057,1596,54397,1019,396,396,5918,226309,800,890,932,490,490,4227,90994,5806,570,181,406,376,2095,420,620,420,376,565,376,9455,8510,490,490,1169,527,2437,796,376,684,1220,1530,620,1954,4824,800,400,932,420,200,1330,1330,1330,1330,1330,1330,1330,1330,1330,1330,1330,1330,1330,1330,1330,1330,1330,1330,1330,1330,1330,1330,1330,1330,1330,1330,2859,3527,2300,1920,525]
NUMBERS.sort()
NUMBERS = NUMBERS[::-1] #reverse list

CUTOFF = 1300 #used to remove values smaller than CUTOFF from the input list
NUMBERS = [val for val in NUMBERS if val >= CUTOFF]

L = len(NUMBERS)
record = [0] * L #initialize an array of L zeroes

print "From the array of " + str(L)+ " elements the following sequences are equal to "+str(SUM)+":"
tsum(0,0)