Five-line solution to the Subset-sum problem (Python)(stackoverflow.com) A five-line Python solution to the subset-sum problem (dynamic programming, pseudopolynomial time): def subset_sum(A, target): T = {0} for i in A: T |= {x + i for x in T} return target in T Seems to be pretty efficient. |