LeetCode 416. 分割等和子集

416. 分割等和子集

解题思路

问题转化

这道题本质上是 0-1 背包问题 的变体。

1. 首先计算数组所有元素的总和 sum。
2. 如果 sum 是奇数，显然无法分成两个相等的整数和子集，直接返回 false。
3. 如果 sum 是偶数，令 target = sum / 2。问题转化为：能否从数组中选出一些数字，使其和恰好为 target。

动态规划

1. 状态定义：
   dp[i] 表示是否存在一个子集，其元素之和为 i。

2. 转移思路：
   遍历数组中的每个数字 num，基于上一轮的 dp 状态，更新当前可能达到的和。
   如果 dp[i] 为 true（即存在和为 i 的子集），那么加上当前数字 num 后，和 i + num 也是可以达成的。

3. 初始化：
   dp[0] = true，表示和为 0 总是可以实现的（即不选任何元素）。

4. 最终结果：
   如果 dp[target] 为 true，说明找到了和为 target 的子集，返回 true。

参考代码

从前往后遍历

class Solution {
    public boolean canPartition(int[] nums) {
        int total_num = 0;
        for(int num : nums) {
            total_num += num;
        }
        if(total_num % 2 != 0) return false;

        int target = total_num / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;

        for(int num : nums) {
            boolean[] dp_temp = dp.clone();
            for(int i = 0; i <= target; i ++) {
                if(dp[i] && i + num <= target) {
                    dp_temp[i + num] = true;
                }
            }
            dp = dp_temp;
            if(dp[target]) return true;
        }
        return dp[target];
    }
}

从后往前遍历

class Solution {
    public boolean canPartition(int[] nums) {
        int total_num = 0;
        for(int num : nums) {
            total_num += num;
        }
        if(total_num % 2 != 0) return false;
        int target = total_num / 2;
        
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for(int num : nums) {
            // boolean[] dp_tmp = dp.clone();
            // for(int i = 0; i <= target; i ++) {
            //     if(dp[i] && i + num <= target) {
            //         dp_tmp[i + num] = true;
            //     }
            // }
            for(int i = target; i >= num; i --) {
                if(dp[i - num]) {
                    dp[i] = true;
                }
            }
            if(dp[target]) return true;
        }
        return dp[target];
    }
}