Partitions with Given Difference

'''
0/1 Knapsack-> Here it wants all the sets combinations whose difference is diff so obviouse one set sum would be x and the other as x+diff
but x+x+diff==sum(arr) so we can try to get one set whose sum is = (sum(arr)-diff)//2, if we get this then other will automatically x+diff
so problem reduced to find all the subsets of target size (sum(arr)-diff//2).

dp table rows will denote all the array indices and column will denote the target we are trying to find. row=0->n-1 and col= 0-> target
so when our target the max number of cols but while summing cur can exceed our target and cur>target is no use of use, because that can't
go in table also(cur> no. of columns) so one more base case at top if cur>target return False


Base case:
1)if cur>target: return False
1) go till the end of the array because if you stop at target, may be some zero we forget to consider for target=5 {0,0,5} as we are coming
from back so when we get 5, we don't go to other 0 but 5+0 is also the 5 only.
so
'''

def fun(arr,cur,n,dp,target):
    if cur>target:
        return 0
    if n<0:
        if cur==target:
            return 1
        return 0
    if dp[n][cur]!=-1:
        return dp[n][cur]
    take=0
    if cur+arr[n]<=target:
        take=fun(arr,cur+arr[n],n-1,dp,target)
    not_take=fun(arr,cur,n-1,dp,target)
    dp[n][cur]=take + not_take
    return dp[n][cur]

class Solution:
    def countPartitions(self, arr, diff):
        total=sum(arr)
        if (total-diff)%2!=0:
            return 0

        target=(total-diff)//2
        dp=[[-1]*(target+1) for _ in range(len(arr))]
        return fun(arr,0,len(arr)-1,dp,target)