# 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: