Fork me on GitHub

LeetCode: partition equal subset sum

LeetCode 416.Partition Equal Subset Sum

LeetCode 416.Partition Equal Subset Sum

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.

This can be regarded as finding a subset whose sum is equal to a specified number (half of the sum here).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def canPartition(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
sum_ = sum(nums)
if sum & 1: # odd number
return False

target = sum_ >> 1

dp = [True] + [False] * target
for num in nums:
for i in reversed(range(num, target+1)):
# target<=i<=num -> i-num>=0
dp[i] = dp[i] or dp[i-num]
return dp[target]

LeetCode 494. Target Sum

You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

1
2
3
4
5
6
7
8
9
10
11
Examples:
- Input: nums is [1, 1, 1, 1, 1], S is 3.
- Output: 5
- Explanation:
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

There are 5 ways to assign symbols to make the sum of nums be target 3.

This can be converted to a subset sum problem:
Let $P$ and $N$ denote positive subset and negative subset,

So the original problem has been converted to a subset sum problem as follows:
Find a subset P of nums such that sum(P) = (target + sum(nums)) / 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def findTargetSumWays(self, nums, S):
"""
:type nums: List[int]
:type S: int
:rtype: int
"""
sum_ = sum(nums)
if sum_ < S or (sum_+S) & 1: # if sum < S or it is odd
return 0
else: # convert to subset sum problem
target = (sum_ + S) >> 1
return self.subsetSum(nums, target)

def subsetSum(self, nums, s):
dp = [1] + [0]*s
for num in nums:
for i in reversed(range(num, s+1)):
dp[i] += dp[i-num]
return dp[s]

References

Thanks for your reward!