'''
Solve the Subset sum problem for a limited number space.

In this example, the limited number space is 3 bit integers.

http://en.wikipedia.org/wiki/Subset_sum_problem

Written for python 3
'''

solution_space = list([frozenset([-1, 1]),
     frozenset([-2, 2]),
     frozenset([-3, 3]),
     frozenset([-3, 1, 2]),
     frozenset([-4, 1, 3]),
     frozenset([-2, -1, 3]),
     frozenset([-4, -1, 2, 3])])



def solve(integer_set):
    solution_dict = dict((frozenset(solution), len(solution)) for solution in solution_space)
    for number in integer_set:
        for solution in solution_space:
            if number in solution:
                matches_countdown = solution_dict[solution] - 1
                solution_dict[solution] = matches_countdown
                if matches_countdown == 0:
                    print(solution)
                    return True
    return False

if __name__ == "__main__":
    # run some tests
    tests = [ [-2, 3], [1,2,3], [1,-1], [-2, -1, 3, 4] ]
    for t in tests:
        print '-' * 10
        print("Set tested: %s, a solution exists: %s" % (t, solve(t)))