a solution to the Subset Sum Problem

[league55]

(The Subset Sum Problem involves determining whether any combination of the elements of a set of integers adds up to zero. For example, for the set {-3, 0, 2, 5, 7, 13} the solution is {-3, 13). For {-4, -3, 1} there is no solution. The problem is considered np-complete. One of the things that means is that you have to test every possible, unique combination of elements in order to determine that the problem has no solution.)

Someone kindly provided me with an algorithm that attempts to solve the Subset Sum Problem, so I thought I'd share it here. This algorithm takes advantage of the fact that you don't necessarily have to test every possible, unique combination in order to find the solution, if there is a solution; and it takes advantage of that fact with clever use of generators.

from itertools import combinations

def solve(input):
    subsets = (
        subset for length in range(1, len(input))
        for subset in combinations(input, length)
    )
    solution = next((subset for subset in subsets if sum(subset) == 0), None)
    if solution is None:
        print('There is no solution for set {}.'.format(input))
    else:
        print('A solution for set {} is {}.'.format(input, solution))