Python elegant top down approach O(N*S) time and space


#1
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]