import sys
sys.setrecursionlimit(10**6)
import functools
class Solution:
# @param A : tuple of integers
# @return an integer
def solve(self, A):
value = sum(A)//2
A = sorted(list(A))
dp = {}
def helper(index,curr_sum):
nonlocal dp
if index == len(A):
dp[(index,curr_sum)] = [curr_sum,0]
return [curr_sum,0]
if (index,curr_sum) in dp:
return dp[(index, curr_sum)]
if curr_sum - A[index]<0:
dp[(index,curr_sum)] = [curr_sum,0]
return [curr_sum,0]
else:
if helper(index+1,curr_sum)[0] > helper(index+1,curr_sum-A[index])[0]:
count_ = 1+helper(index+1,curr_sum-A[index])[1]
min_ = helper(index+1,curr_sum-A[index])[0]
if helper(index+1,curr_sum)[0] == helper(index+1,curr_sum-A[index])[0]:
count_ = min(helper(index+1,curr_sum)[1],1+helper(index+1,curr_sum-A[index])[1])
min_ = helper(index+1,curr_sum-A[index])[0]
if helper(index+1,curr_sum)[0] < helper(index+1,curr_sum-A[index])[0]:
count_ = helper(index+1,curr_sum)[1]
min_ = helper(index+1,curr_sum)[0]
dp[(index,curr_sum)] = [min_,count_]
return dp[(index, curr_sum)]
helper(0,value)
return dp[(0,value)][1]
