416. 分割等和子集

416.分割等和子集

题目

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

1
2
3
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

1
2
3
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100

思路

动态规划思路

1. 问题转化

  • 如果整个数组的和 sum 是奇数，直接返回false（因为奇数无法均分成两个整数和）。
  • 如果 sum 是偶数，问题转化为：是否存在一个子集，其和等于 sum / 2。

2. 定义状态

  • 定义一个布尔数组 dp，其中 dp[i] 表示：能否用数组中的某些数凑出和 i。
    • dp[i] = true：能凑出 i。
    • dp[i] = false：不能凑出i。
  • 初始化：dp[0] = true（因为和为0 的子集是空集，总是存在）。

3. 状态转移

  • 遍历数组中的每一个数 num，然后从 target 倒序更新 dp 数组（避免重复计算）：
    • 对于每个 i（从 target 到 num），如果 dp[i - num] 是true，说明可以通过加上 num 得到 i，因此dp[i] = true。
    • 关键公式：dp[i] = dp[i] || dp[i - num]。

4. 最终结果

  • 返回 dp[target]（即是否能凑出 sum / 2）。

完整代码

1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean canPartition(int[] nums) {
//如果整个数组的和sum是奇数，直接返回false（因为奇数无法均分成两个整数和）。
//如果sum是偶数，问题转化为：是否存在一个子集，其和等于sum/2。
        int sum=Arrays.stream(nums).sum();
        if (sum%2!=0)
            return false; //总和为奇数,返回false
        int ans=sum/2;
        boolean[] dp=new boolean[ans+1];
        dp[0]=true;
        for(int num:nums){
            for(int i=ans;i>=num;i--){
                if(dp[i-num])   dp[i]=true;
            }
            if(dp[ans]) return true;
        }
        return dp[ans];
    }
}