count the number of subset with the given difference [DP]

Suraj_Panwar · March 26, 2023
def Subset(arr,sum,n):
    
    t=[[0 for x in range(sum+1)] for x in range(n+1)]
    
    
    for i in range(sum+1):
        t[0][i]=0
    for i in range(n+1):
        t[i][0]=1
           
    for i in range(1,n+1):
        for j in range(1,sum+1):
            if arr[i-1]<=j:
                t[i][j]=t[i-1][j] + t[i-1][j-arr[i-1]]
            elif arr[i-1]>j:
                t[i][j]=t[i-1][j]
    return t[n][sum]
    
    
arr=[3,2,1,5,4]
diff=2
summ=(diff+sum(arr))//2

n=len(arr)
print(Subset(arr,summ,n))
Output

Comments

Please sign up or log in to contribute to the discussion.