Five-line solution to the Subset-sum problem (Python) (opens in new tab)

(stackoverflow.com)

2 pointsvarrakesh13y ago1 comments

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.

1 comments

Interesting 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])

j / k navigate · click thread line to collapse

1 comments

adlpz13y ago

Interesting 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])

j / k navigate · click thread line to collapse