leetcode hot100【Leetcode 416.分割等和子集】java实现

Leetcode 416.分割等和子集

题目描述

给定一个非负整数的数组 nums ，你需要将该数组分割成两个子集，使得两个子集的元素和相等。如果可以分割，返回 true ，否则返回 false。

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

Java 实现代码

public class Solution {public boolean canPartition(int[] nums) {int sum = 0;for (int num : nums) {sum += num;}// 如果总和是奇数，不能平分if (sum % 2 != 0) {return false;}int target = sum / 2;boolean[] dp = new boolean[target + 1];dp[0] = true; // 和为 0 总是能做到for (int num : nums) {// 从后往前更新 dp 数组for (int j = target; j >= num; j--) {dp[j] = dp[j] || dp[j - num];}}return dp[target];}
}

解题思路

这个问题可以转化为0/1背包问题，我们需要检查是否能在数组中找到一个子集，使得这个子集的和为 sum(nums) / 2。如果可以找到，剩下的元素自然就是另一个子集，两者和相等。

具体步骤：

1. 首先检查数组总和是否为偶数。如果总和为奇数，直接返回 false，因为无法将其平均分配成两个相等的部分。

2. 动态规划：定义一个布尔数组 dp，其中 dp[i] 表示是否能够从数组中选取若干个元素，使得它们的和为 i。初始化时，dp[0] = true（因为和为 0 总是可以通过选择空集合得到）。

3. 遍历数组中的每个元素，对于每个元素，从后往前更新 dp 数组。如果 dp[j - num] 为 true，则说明可以通过添加 num 这个元素使得和为 j，所以设置 dp[j] = true。

4. 最终，判断 dp[target] 是否为 true，其中 target = sum(nums) / 2。

复杂度分析

• 时间复杂度：O(n * target)，其中 n 是数组 nums 的长度，target 是目标值（即 sum(nums) / 2）。需要遍历每个元素，并且对于每个元素，更新 dp 数组的每个状态。

• 空间复杂度：O(target)，我们只需要一个大小为 target + 1 的布尔数组 dp 来存储状态。

执行过程示例

假设 nums = [1, 5, 11, 5]。

1. 计算数组总和：sum = 1 + 5 + 11 + 5 = 22，所以目标是 target = sum / 2 = 11。

2. 初始化 dp 数组：dp[0] = true，其余元素初始化为 false。 dp = [true, false, false, false, false, false, false, false, false, false, false, false]

3. 遍历数组元素，更新 dp 数组：

   • 处理元素 1：

     dp[1] = true  // 可以通过选择 1 得到和 1
     dp = [true, true, false, false, false, false, false, false, false, false, false, false]
     

   • 处理元素 5：

     dp[6] = true  // 可以通过选择 5 得到和 6
     dp[5] = true  // 可以通过选择 5 得到和 5
     dp = [true, true, false, false, false, true, true, false, false, false, false, false]
     

   • 处理元素 11：

     dp[11] = true  // 可以通过选择 11 得到和 11
     dp = [true, true, false, false, false, true, true, false, false, false, false, true]
     

   • 处理元素 5：

     dp[10] = true  // 可以通过选择 5 得到和 10
     dp[5] = true   // 可以通过选择 5 得到和 5
     dp = [true, true, false, false, false, true, true, false, false, false, true, true]
     

4. 最终，dp[11] 为 true，说明可以分割成两个和为 11 的子集，因此返回 true。