Minimum Subset Sum Difference

'''
0/1 Knapsack-> Here the rows are all the elments indices and columns would be the range of minimum to maximum difference so row=n and col=sum(arr)+1
Minimum difference between sum of two partitioned sets can be 0 and maximum can be sum(arr) when all the elements in one set.
- we will keep the cur variable which will have 0 in beginning and shows the sum of the current set.
- We can traverse either when our cur_sum> sum(arr)//2 because once half of the sum is there, adding more numbers will make the difference bigger.
- We can stop when we skipped a lot of elements so cur< sum(arr)//2 but you reach at the end of the arr(ie. n<0) because no elements left now.
- In the above two coditon set1_sum=cur, set2_sum=sum(arr)-cur so their difference= abs(total-cur-cur) ie abs(total-2*cur)
- Once we get values from take and not_take, we will update the dp table with the minimum value of them.

Base Case:
1)When cur>sum(arr)//2 or n<0: return abs(total-2*cur)
'''


def fun(arr, cur, n,dp,total):
    if cur> total//2:
        return abs(total-2*cur)
    if n<0:
        return abs(total-2*cur)

    if dp[n][cur]!=-1:
        return dp[n][cur]
    take=fun(arr,cur+arr[n],n-1,dp,total)
    not_take=fun(arr,cur,n-1,dp,total)
    dp[n][cur]=min(take,not_take)
    return dp[n][cur]

class Solution:
    def minDifference(self, arr):
        l,r=0,sum(arr)+1
        dp=[[-1]*r for _ in range(len(arr))]
        return fun(arr,0,len(arr)-1,dp,sum(arr))