Solution to LeetCode 416 Partition Equal Subset Sum and LeetCode 1049 Last Stone Weight II.
LeetCode 416
Partition Equal Subset Sum (Medium) [link]
We want to find a subset of numbers whose summation is equal to half of the total summation.
This problem can be seen as a 0-1 knapsack problem. The volume of knapsack is sum/2. The numbers can be seen as values or weights of items. If the knapsack can be taken up by some numbers, we are done. We assume items are not allowed to be repeatedly put into the knapsack.
Define dp[j] array as the maximal total value of items taken by a knapsack with j capacity.
The recurrence relation of o-1 knapsack problem is dp[j] = max(dp[j], dp[j-w[i]]+v[i]). Since w[i] and v[i] are the same as num[i] in this problem, the recurrence relation is dp[j] = max(dp[j], dp[j-num[i]]+num[i]).
The base case is dp[0]=0 when the capacity is none. The dp array is initiated to have a size of 10001., because the values in an array <= 100 and the length of array is <= 200. So the total is <=20000, while the half is <=10000. Therefore, we can safely initialize dp=[0]*10001. If dp[j]==j, the answer to the question is yes.
The time complexity is O(n^2). The space complexity is O(n).
class Solution:
def canPartition(self, nums: List[int]) -> bool:
target = sum(nums)
if target % 2 == 1: return False
target //= 2
dp = [0]*10001
for i in range(len(nums)):
for j in range(target, nums[i]-1, -1):
dp[j] = max(dp[j], dp[j-nums[i]]+nums[i])
return target == dp[target]
Note that for 1d-array dp[j], the outer for loop is iterating items, the inner for loop is iterating knapsack capacities. The outer for loop is iterating in the ascending order, the inner for loop is iterating in the descending order. Otherwise, items can be counted more than once.
LeetCode 1049
Last Stone Weight II (Medium) [link]
We can consider this problem as a 0-1 knapsack problem. The idea is to have two groups of stones with as same total weights as possible. In this case, after smashing them, the remaining stone has the smallest weight. The weight and the value are both stone[i].
Define dp[j] as the knapsack with capacity j. The recurrence relation for the 0-1 knapsack problem is dp[j] = max(dp[j], dp[j-w[i]] + v[i]). The recurrence relation for this problem is dp[j] = max(dp[j], dp[j-stone[i]] + stone[i]).
The base case is dp[0]=0 for zero capacity. Since 1 <= len(stones) <= 30，1 <= stones[i] <= 1000, the max weight is 30*1000=30000 . Therefore, the length of dp array can be safely initiated to be 15001.
class Solution:
def lastStoneWeightII(self, stones: List[int]) -> int:
total = sum(stones)
target = total // 2
dp = [0] * 150001
for i in range(len(stones)):
for j in range(target, stones[i] - 1, -1):
dp[j] = max(dp[j], dp[j-stones[i]]+stones[i])
return total - 2 * dp[target]
