leetcode 416 Partition Equal Subset Sum
z
 2019-04-11 11:13:17  

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:

1
2
3
4
5
Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

1
2
3
4
5
Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.
  • dfs (time exceed)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        if (nums == null) return false;
        for (int i: nums) sum += i;
        if (sum % 2 != 0) return false;
        sum = sum/2;
        return helper(nums, sum, 0);
    }
    
    public boolean helper(int[] nums, int target, int k) {
        if (target == 0)
            return true;
        if (target < 0)
            return false;
        for (int i=k; i<nums.length; i++) {
            if (helper(nums, target-nums[i], i+1))
                return true;
        }
        return false;
    }
}
  • 0/1 backpack
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
29
30
31
class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        if (nums == null) return false;
        for (int i: nums) sum += i;
        if (sum % 2 != 0) return false;
        sum = sum/2;
        boolean[] dp = new boolean[sum+1];
        dp[0] = true;
        // 如果采用以下方案，对每一个sum，nums[i]是有可能被复用的，
      	// 因此，需要把对nums的循环放到外层。
        // for(int i=1; i<= sum; i++) {
        //     for (int j: nums) {
        //         if (i-j >= 0) {
        //             dp[i] = dp[i] || dp[i-j];
        //         }
        //     }
        // }
      
        for (int i: nums) {
            // 同样，当对sum的循环是从小到大时，nums[i]同样也可以被服用，
          	// 比如，当nums[0] = 1时，后续的sum[]都会为true
            // 从大到小的话，只有最小的dp[j-i]才有可能被设为true
            for (int j=sum; j>=i; j--) {
                if (j >= i)
                    dp[j] = dp[j] || dp[j-i];
            }
        }
        return dp[sum];
    }
}