🌕 🌗 416. 分割等和子集

难度: 🌕 🌗

问题描述

---

解法

class Solution {
    public boolean canPartition(int[] nums) {
        // 思路：
        // 背包问题 -- 能否填充背包使得背包价值总和为总和的一半
        int sum = 0;
        for(int i : nums) {
            sum += i;
        }
        if((sum & 1) == 1) {
            return false;
        } 
        // sum 是偶数
        sum >>= 1;
        // 目标：尽可能填充背包，使得背包价值尽可能大，如果最终能够 == 总和的一半，说明可以分割等和子集
        // dp[i] = dp[i - [j]] + [j]
        int len = nums.length;
        int[] dp = new int[sum + 1];
        // 先遍历背包，再遍历物品，从而保证每个物品最多只能拿一次
        for(int j = 0; j < len; j ++) {
            for(int i = sum; i - nums[j] >= 0; i --) {
                dp[i] = Math.max(dp[i], dp[i - nums[j]] + nums[j]);
            }
        }
        return dp[sum] == sum;
    }
}

---

输出