Partition Equal Subset Sum

Problem

Return True if nums can be split into two subsets with equal sums, and False otherwise.

If the total is odd the answer is immediately False; otherwise run subset-sum dynamic programming for half the total, using each number at most once. An empty list sums to zero and can be partitioned.

Hint

This is the subset-sum problem on half the total; sweep capacities downward so each number is used once.

Test cases

case 1

in: [[1,5,11,5]]

expected: true

case 2

in: [[1,2,3,5]]

expected: false

case 3

in: [[]]

expected: true

case 4

in: [[1]]

expected: false

case 5

in: [[2,2,2,2]]

expected: true

Starter codePython

def can_partition(nums):
    # Your code here
    pass

5 test cases · run your code against them in the editor