算法训练Day41|416. 分割等和子集

 1class Solution {
 2    public boolean canPartition(int[] nums) {
 3        int sum = 0;
 4        for (int num : nums) {
 5            sum += num;
 6        }
 7        if (sum % 2 != 0) {
 8            return false;
 9        }
10        int target = sum / 2;
11        // target 代表重量和价值 则dp[] 数组要达到target，需要创建数组范围为：[0, target]
12        int[] dp = new int[target + 1];
13        for (int i = 0; i < nums.length; i++) { // 先遍历物品
14            for (int j = target; j >= nums[i]; j--) {
15                // 再遍历背包
16                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
17            }
18        }
19        return dp[target] == target;
20    }
21}