Meet in the Middle Sum Count

Problem

Count the subsets of nums, by index and including the empty subset, whose elements sum to target.

Split nums in half, enumerate all subset sums of each half, and for every sum in the second half add the count of target minus that sum in the first table. Suitable for inputs up to about 20 elements.

Hint

Duplicate sums are counted with their multiplicity, which is what the hash table stores.

Test cases

case 1

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

expected: 2

case 2

in: [[0,0],0]

expected: 4

case 3

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

expected: 6

case 4

in: [[],0]

expected: 1

case 5

in: [[5],5]

expected: 1

Starter codePython

def meet_in_middle_sum_count(nums, target):
    # Your code here
    pass

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