Yekun's Note

Machine learning notes and writeup.

Fork me on GitHub

LeetCode: partition equal subset sum

Posted on In , , Disqus:

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