leetcode-416. 分割等和子集

0-1背包问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int total = 0;
        for(int i = 0; i < nums.length; i++){
            total += nums[i];
        }

        if(total % 2 == 1){
            //总和为奇数
            return false;
        }

        int half = total / 2;

        int[] dp = new int[half+1];
        for(int i = 1; i <= n; i++){
            for(int j = half; j >= nums[i-1]; j--){
                dp[j] = Math.max(dp[j], dp[j-nums[i-1]] + nums[i-1]);
            }
        }
        return dp[half] == half ? true : false;
    }
}