416. 分割等和子集

01背包

import java.util.Arrays;

class Solution {
    public boolean canPartition(int[] nums) {

        int sum = Arrays.stream(nums).sum();

        /**
         * 如果所有数的和为奇数，则不能平分
         */
        if (sum % 2 != 0){
            return false;
        }

        int target = sum / 2;

        /**
         * dp[j]定义为容量为j的背包中，能放入的最大数值和，最大值为target
         * 每个数字的价值和重量都是本身，初始化值都为0
         */
        int[] dp = new int[target + 1];

        for (int i = 1; i <= nums.length; i++) {

            for (int j = target; j >= nums[i - 1]; j--) {
                dp[j] = Math.max(dp[j], dp[j - nums[i - 1]] + nums[i - 1]);
            }
        }

        /**
         * 如果最后一个位置的最大数值和等于max，说明刚好这个子集满足条件
         */
        return dp[target] == target;
    }
}

/**
 * 时间复杂度 O(n^2)
 * 空间复杂度 O(n)
 */

https://leetcode-cn.com/problems/partition-equal-subset-sum/