Leetcode: Partition Equal Subset Sum

Partition Equal Subset Sum



Similar Problems:


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.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


// Blog link: https://code.dennyzhang.com/partition-equal-subset-sum
// Basic Ideas: hashmap
//  If we can find some combination with the sum as half of the sum, return true
// Complexity: Time O(n*n), Space O(n)
func canPartition(nums []int) bool {
    sum := 0
    for _, num := range nums {
        sum += num
    }
    if (sum%2) != 0 {
        return false
    }
    target := sum/2
    m := map[int]bool{}
    for _, num := range nums {
        if num == target {
            return true
        }
        if num > target {
            return false
        }
        l := []int{num}
        for key, _ := range m {
            if num+key == target {
                return true
            }
            l = append(l, num+key)
        }

        for _, val := range l{
            m[val] = true
        }
    }
    return false
}
## Blog link: https://code.dennyzhang.com/partition-equal-subset-sum
## Basic Ideas: hashmap
##
## Complexity: Time O(n*n), Space O(n)
class Solution(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        import copy
        sum_value = sum(nums)
        if sum_value%2 != 0: return False
        target = sum_value/2
        print(sum_value, target)
        value_set = set([])
        for num in nums:
            tmp_set = copy.deepcopy(value_set)
            for v in value_set:
                if v+num == target: return True
                if v+num < target:
                    tmp_set.add(v+num)
            if num == target: return True
            if num < target:
                tmp_set.add(num)
            value_set = tmp_set
        return False
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.