Count of Subsets sum

'''
0/1 Knapsack-> subset sum exist or not?
There subset sum was returning the True or False but here we need the count of those subsets also
so our dp table will be having the numbers here.and here we are adding the take and not_take cases
to get the total number of subsets

Base conditon:
1.Go till the array complete unlike the subset sum because for eg. {0,0,1} you start
from the right side, so if you get cur==target and then you return, in that case
{0,0,1},{0,1} cases will be missed and {1} this case will be also counter because our
recursion will take the skip those two zeros route.
2.if cur==target: return 1 saying got one subset
'''
def fun(arr, target, n, dp):
    if n < 0: #if you are going till the n<0 suppose the arr is {0,0,1} so when you reach at the 1st or 0th index there either you will select or not select that will cover {0},{0},{0,0} cases also
        if target == 0:
            return 1
        return 0

    if dp[n][target] != -1:
        return dp[n][target]

    take, not_take = 0, 0

    if arr[n] <= target:
        take = fun(arr, target - arr[n], n - 1, dp)

    not_take = fun(arr, target, n - 1, dp)

    dp[n][target] = take + not_take
    return dp[n][target]


class Solution:
    def perfectSum(self, arr, target):
        dp = [[-1] * (target + 1) for _ in range(len(arr))]
        return fun(arr, target, len(arr) - 1, dp)