Partition Equal Subset Sum

1. The obvious way

   Try every subset: O(2^n).

2. The key insight

   Let half = total / 2 (stop if the total is odd). Keep a set of reachable sums, starting with {0}. For each number add (sum + number) for every reachable sum not above half. Answer: is half reachable?

3. The algorithm
   1. Odd total: False. half = total / 2.
   2. reachable = {0}.
   3. For each number add old sum + number to reachable (at most half).
   4. Return whether half is in reachable.

Watch it run

reachable: 0

def can_partition(nums):
    total = sum(nums)
    if total % 2 == 1:
        return False                                    # cannot be split into two equal whole halves
    half = total // 2
    reachable = {0}                                     # totals we can make with some of the packets
    for packet in nums:
        reachable |= {made + packet for made in reachable if made + packet <= half}
    return half in reachable

Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.