Partition Equal Subset Sum

'''
0/1 Knapsack and same like problem subset sum
here target=sum(arr)//2 and one cache if sum is not even then half of sum can't be done by splitting array so direcly return False.
'''

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 canPartition(self, nums: List[int]) -> bool:
        if sum(nums) % 2 != 0:
            return False

        target = sum(nums) // 2
        dp = [[-1] * (target + 1) for _ in range(len(nums))]

        return fun(nums, target, len(nums) - 1, dp)