educative.io

Alternative solution with DP

Courses
,
#1

I believe Igor’s non-DP solution is superior, but just for fun:

def can_partition(nums):
  diffs = set([0])
  for n in nums:
    diffs2 = set()
    for diff in diffs:
      diffs2.add(abs(diff + n))
      diffs2.add(abs(diff - n))
    diffs = diffs2
  return min(diffs)
1 Like
#2

For someone wondering about Igor’s solution.

Here it is: Do we need DP here?