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:

  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.
class Solution {
    public boolean canPartition(int[] nums) {
        int le = nums.length;
        int cur = 0;
        for(int i: nums) cur += i;
        if((cur & 1) == 1) return false;
        boolean[][] dp = new boolean[le+1][cur/2+1];
        dp[0][0] = true;
        for(int i = 0; i < le+1; i++) dp[i][0] = true;
        for(int i = 1; i < le+1; i++){
            for(int j = 1; j < cur/2 + 1; j++){
                dp[i][j] = dp[i-1][j];
                if(nums[i-1] <= j) dp[i][j] = dp[i][j] || dp[i-1][j - nums[i-1]];
            }
        }
        return dp[le][cur/2];
    }
}

一个很好的背包问题,要两个subset相等,那就说明一个subset的和是sum/2.

然后有dp数组 dp[ length+1] [ sum/2 + 1]。dp数组dp[i][j]意思是有i个nums,能从中形成一个subset使和等于j,首先初始化dp,dp【i】【0】== true,因为sum == 0时无论是什么subset都可以(空集)

同时注意,nums[ i - 1 ] <= j时才需要更新,因为当前value要小于等于背包的大小。

dp【i】【j】 = dp【i-1】【j】(不选nums【i】) || dp【i - 1】【j - nums【 i - 1】(选nums【i - 1】)

最后返回dp的右下角

上一篇:使用位运算得到所有子集


下一篇:递归-子集和问题