Description
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:
- Each of the array element will not exceed 100.
- 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.
Solutions
1. DP-01 Knapsack
要知道怎么转换这个问题,其实该题就是在数组中找到加和为总加和一半的若干个数。
dp[i][j] 表示前 i 个数能否组成加和为 j 的组合(可以不用全选前 i 个数)。
# Time: O(mn)
# Space: O(mn)
class Solution:
def canPartition(self, nums: List[int]) -> bool:
if not nums:
return False
sumA = sum(nums)
# if the sum is odd, return False
if sumA & 1 == 1:
return False
sumA = sumA >> 1
n = len(nums)
dp = [[False for _ in range(sumA + 1)] for _ in range(n + 1)]
dp[0][0] = True
for i in range(1, n + 1):
dp[i][0] = True
for j in range(1, sumA + 1):
dp[0][j] = False
for i in range(1, n + 1):
for j in range(1, sumA + 1):
if nums[i - 1] <= j:
dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]
else:
dp[i][j] = dp[i - 1][j]
return dp[n][sumA]
# Runtime: 2180 ms, faster than 10.05%
# Memory Usage: 16.8 MB, less than 9.09%
优化,要搞清楚为什么这么优化!
# Time: O(mn)
# Space: O(m)
class Solution:
def canPartition(self, nums: List[int]) -> bool:
if not nums:
return False
sumA = sum(nums)
# if the sum is odd, return False
if sumA & 1 == 1:
return False
sumA = sumA >> 1
dp = [False for _ in range(sumA + 1)]
dp[0] = True
for num in nums:
for j in range(sumA, -1, -1):
if num <= j:
dp[j] = dp[j] or dp[j - num]
return dp[sumA]
# Runtime: 884 ms, faster than 42.07%
# Memory Usage: 12.7 MB, less than 100.00%