```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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 ``` ```''' A minimum solution space finder for the "subset sum problem". This gets messy when you try to work with 5 bits and up, maybe pypy can make it work. written for python 3 with inspiration from http://www.reddit.com/r/programming/comments/d1oay/solve_p_vs_np/ ''' from itertools import combinations from pprint import pprint BITS = 3 def build_numbers_of_signed_int(num_of_bits): maximum = 2 ** (num_of_bits - 1) - 1 minimum = -1 - maximum numbers = set(range(minimum, maximum + 1)) numbers.remove(0) # remove the trivial solutions return numbers def get_solution_sets(numbers_space): zero_sets = [] for set_size in range(2, len(numbers_space) + 1): for combo in combinations(numbers_space, set_size): if sum(combo) == 0: zero_sets.append(set(combo)) return zero_sets def minimize_solution_sets(solution_sets): unique_solutions = solution_sets[::] for solution in solution_sets: is_unique = True for other_solution in unique_solutions: if solution.issubset(other_solution) and solution != other_solution: unique_solutions.remove(other_solution) break return unique_solutions def main(): solution_dimensions = [] for bits in range(2,5): signed_ints = build_numbers_of_signed_int(bits) sol_sets = get_solution_sets(signed_ints) min_sets = minimize_solution_sets(sol_sets) solution_dimensions.append((bits, len(sol_sets), len(min_sets))) pprint(sol_sets) pprint(min_sets) pprint(solution_dimensions) if __name__ == "__main__": main() ```
 ```1 2 3 4 ``` ```Traceback (most recent call last): Line 9, in from itertools import combinations ImportError: cannot import name combinations ```