416. Partition Equal Subset Sum

[fockspaces]

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

Example 1:

Input: nums = [1,5,11,5] Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11]. Example 2:

Input: nums = [1,2,3,5] Output: false Explanation: The array cannot be partitioned into equal sum subsets.

Constraints:

1 <= nums.length <= 200 1 <= nums[i] <= 100

[fockspaces]

1. 判斷能否分成兩部分（總和偶數）
2. 總和一半的值即為要找的目標
3. 開 dp 求投硬幣的值

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2 != 0:
            return False
        target = total // 2

        dp = [False for i in range(target + 1)]
        dp[0] = True

        for num in nums:
            for i in range(target, target - num, -1):
                dp[i] = dp[i] or dp[i - num]
        return dp[target]

[fockspaces]

target - num 改為 num - 1 更直觀，end 是不包含的值，在這邊最低算到 i = 0，因此寫 num - 1

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2 != 0:
            return False
        target = total // 2

        dp = [False for i in range(target + 1)]
        dp[0] = True

        for num in nums:
            for i in range(target, num - 1, -1):
                dp[i] = dp[i] or dp[i - num]
        return dp[target]