力扣416题 分割等和子集 Java语言版

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        int n = nums.length;
        for(int i=0; i<n; i++){
            sum += nums[i];
        }
        if(sum % 2 == 1){
            return false;
        }
        int bagSize = sum / 2;
        // 1.确定dp数组
        int[] dp = new int[bagSize+1];
        // 2.确定递推关系
        /**
            dp[j] = Math.max(dp[j],dp[j-nums[i]] + nums[i]);
         */
        // 3.初始化
        dp[0] = 0;
        // 4.遍历顺序 先遍历物品,再遍历背包 背包降序
        for(int i=0; i<n; i++){
            for(int j=bagSize; j>=nums[i]; j--){
                dp[j] = Math.max(dp[j],dp[j-nums[i]] + nums[i]);
            }
        }
        return dp[bagSize] == bagSize;
    }
}
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

运行结果：