2 ms·
Five-line solution to the Subset-sum problem (Python)
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.
- adlpz 14y agoInteresting to see actual use of sets on Python. For those like me not familiar with the syntax there, the OR-ing (|=) is just Union minus Intersection (because all elements of a Set are unique). >>> {1,2,3} | {2,4,6} set([1, 2, 3, 4, 6]) By the way, AND-ing would be a straight intersection >>> {1,2,3} & {2,4,6} set([2])