Subset Sum

'''
0/1 knapsack variation: Either take if cur_sum<target or not take
dp table dimension: n*(sum+1) which means rows are 0->n-1 which represents all the element indices
and column represents the sum from 0-> sum so here dp[i][j] will contain either True or False and
it says-> is it possible to get the target using the 0->ith indices elements' sum.

Base Case:
1.cur_sum==Targe->return True
2.if n<0 return False because we didn't reach target yet
3.add the current element only when cur_sum<target
'''
def fun(arr, target, n, dp):
    if target == 0:
        return True

    if n < 0:
        return False

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

    take, not_take = False, False

    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 or not_take
    return dp[n][target]

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