```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 ``` ```''' 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))) ```