A subset of Python (30 Jun 2013)

Over the years, I collected implementations of an algorithm to solve the subset sum problem in various languages. A few days ago, I experimented a little with Python, and here is the deplorably non-idiomatic and naïve result - apologies offered.

import random
import array
import sys

numbers = array.array('i')
flags = array.array('c')
solutions = 0

def find_solutions(k, target_sum):
    global solutions

    if target_sum == 0:
        print "  Solution:",
        for i in range(0, len(numbers)):
            if flags[i] != 0:
                print numbers[i],
        print
        solutions = solutions + 1
    else:
        if k < len(numbers):
            if (numbers[k] * (len(numbers)-k+1)) >= target_sum:
                if target_sum >= numbers[k]:
                    flags[k] = 1
                    find_solutions(k+1, target_sum - numbers[k])
                    flags[k] = 0
                find_solutions(k+1, target_sum)

def find_subset_sum(target_sum):
    global solutions
    global flags
    print "Subsets which sum up to %s:" % target_sum
    flags = [0] * len(numbers)
    find_solutions(0, target_sum)
    print "Found", solutions, "different solutions"

def subset_sum_test(size):
    global numbers
    total = 0

    print "Random values:\n  ",
    for i in range(0, size):
        numbers.append(random.randint(0, 1000))
        total = total + numbers[i]
        print numbers[i],
    print

    numbers = sorted(numbers, reverse = True)
    target_sum = total/2
    find_subset_sum(target_sum)

subset_sum_test(15 if len(sys.argv) < 2 else int(sys.argv[1]))

---

When asked for a TWiki account, use your own or the default TWikiGuest account.

---