卖萌的弱渣

I am stupid, I am hungry.

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:

Both the array size and each of the array element will not exceed 100.

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.

Solution

  • DFS + Hash_map(nums[i], appear nums)
(Partition-Equal-Subset-Sum.java) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public class Solution {
    public boolean canPartition(int[] nums) {
        HashMap<Integer, Integer> hash_map = new HashMap<Integer, Integer>();
        int sum = 0;
        for(int num: nums){
            if(hash_map.containsKey(num))
                hash_map.put(num, hash_map.get(num)+1);
            else
                hash_map.put(num,1);
            sum += num;
        }
        if(sum%2 !=0) return false;
        return helper(hash_map, sum/2);
    }

    // dfs
    public boolean helper(HashMap<Integer, Integer> hash_map, int target){
        if(hash_map.containsKey(target) && hash_map.get(target) > 0) return true;
        for(int num: hash_map.keySet()){
            if(num < target && hash_map.get(num) > 0){
                hash_map.put(num, hash_map.get(num)-1);
                if(helper(hash_map, target-num)) return true;
                hash_map.put(num, hash_map.get(num)+1);
            }
        }
        return false;
    }
}