'''
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()

Traceback (most recent call last):
  Line 9, in <module>
    from itertools import combinations
ImportError: cannot import name combinations