Solutions

# Take or skip each number, and check if we can achieve the target sum (half of total sum). Top-down DP with memoization, bottom-up DP or DP with hashset.
# dp

# Top-down DP with memoization - O(n * sum(nums)) time, O(n * sum(nums)) space
def canPartition(nums: list[int]) -> bool:
    if sum(nums) % 2 != 0:
        return False

    half = sum(nums) // 2
    dp = {}

    def dfs(i: int, curr: int) -> bool:
        if curr == half:
            return True
        if i == len(nums):
            return curr == half
        if (i, curr) in dp:
            return dp[(i, curr)]

        # pick or skip the current element
        dp[(i, curr)] = dfs(i+1, curr) or dfs(i+1, curr + nums[i])
        return dp[(i, curr)]

    return dfs(0, 0)


# Bottom-up DP - O(n*sum(nums)) time, O(n*sum(nums)) space 
def canPartition(nums: list[int]) -> bool:
    if sum(nums) % 2 != 0:
        return False

    target = sum(nums) // 2
    N = len(nums)

    # db[i][j] = using the first i numbers, can we achieve sum j
    dp = [[False] * (target + 1) for _ in range(N + 1)]

    # Base case: 0 sum is always achievable, with any subarray
    for i in range(N + 1):
        dp[i][0] = True

    for i in range(1, N+1):
        for j in range(1, target+1):
            # if the current number is <= j (current sum), pick it OR skip it
            if nums[i-1] <= j:
                dp[i][j] = dp[i-1][j] or dp[i-1][j - nums[i-1]]
            else:
                # if the current number is > j (current sum), skip it
                dp[i][j] = dp[i-1][j]

    return dp[N][target]



# DP with hashset - O(n * sum(nums)) time, O(sum(nums)) time
def canPartition(nums: list[int]) -> bool:
    total = sum(nums)
    if total % 2 != 0:
        return False

    target = total // 2
    # dp contains all subsets sums that can be formed using the processed numbers
    dp = set()
    dp.add(0) # sum 0 is always possible

    for n in nums: # order doesn't matter
        # add n to all existing sums in dp, and add those new sums to dp
        next_dp = set() # must use a new set to avoid modifying dp while iterating over it
        for t in dp:
            next_dp.add(t)      # skip current number
            next_dp.add(t + n)  # take current number
        dp = next_dp

    return target in dp