Daily LeetCode 416. Partition Equal Subset Sum

https://leetcode.com/problems/partition-equal-subset-sum/

Medium

问题描述：

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

1. Each of the array element will not exceed 100.
2. The array size will not exceed 200.

Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

思路及代码：

给定一个只含有正数的数组，我们要判断该数组是否能够拆分成两部分，保证两部分的和相等。

既然是两部分的和相等，那么目标和一定是整个数组的和除2，我们先求整个数组的和，判断除2后是否为整数，若不是整数，那么直接返回False。

和除2为整数时，此时问题就转化为，我们需要将数组切分为两个和均为sum/2的部分，维护一维数组dp，dp[i]表示原数组是否能够取出若干数字，使得这些数字的和为i。找出数字的和为sum/2，也保证剩下的部分和也为sum/2。

有了dp数组，我们就要确定状态转移方程，dp[i]能否为True，与dp[i-当前取出数字]是否为True相关。

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        sum = 0
        for num in nums:
            sum += num

        if sum % 2 == 0:
            sum = int(sum / 2)
        else:
            return False

        dp = [False] * (sum + 1)
        dp[0] = True

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

        return dp[sum]