【leetcode】—416.分割等和子集

✏️ 关于专栏：专栏用于记录 LeetCode 中做题与总结

分割等和子集

▐ 题目描述

题目链接：分割等和子集

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

▐ 题目示例

示例 1：

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

示例 2：

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

▐ 题目提示

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

▐ 思路&代码

方法：动态规划

思路：我们可以把这个问题转化为一个子集和问题。

• 设数组总和为 $sum$，若是 $sum$奇数，则不可能分成两个相等的子集，直接返回 $false$。

• 若是偶数，目标是找出一个子集，它的元素和为 $sum/2$。

• 如果$nums$中最大的元素$max\_element$是大于$sum/2$​​,则不可能分成两个相等的子集，直接返回 $false$。

我们使用一个 布尔型数组 $dp$，它的索引表示某个子集和的目标值，值为 true 表示当前和是可能的，值为 $false$表示当前和是不可达的。

$dp$含义：

$dp[i]$表示是否存在子集，其和为$i$.

$dp$初始化：

$dp[0]=true$

(不选取任何元素)

$dp$​状态转移方程：

状态定义：

• dp[j] 表示是否可以通过选取一些元素使得它们的和为 j。
  • 初始状态：dp[0] = true，表示和为 0 的子集总是可能的（即不选择任何元素）。
  • 其他 dp[j] 初始化为 false，表示当前我们还不能形成和为 j 的子集。

状态转移：

对于每个元素 num，我们尝试更新 dp 数组。如果我们能通过之前的某些数字组合成和为 j - num 的子集，那么加上当前数字 num 就可以组成和为 j 的子集。

Example:

代码：

class Solution {
public:bool canPartition(vector<int>& nums) {int sum = 0;for (int num : nums) {sum += num;}// 如果总和是奇数，则不可能划分成两个相等子集if (sum % 2 != 0) return false;int target = sum / 2;int maxElement = *max_element(nums.begin(),nums.end());if(maxElement > target) return false;// 定义一维dp数组，dp[i]表示是否存在子集，其和为ivector<bool> dp(target + 1, false);dp[0] = true; // 和为0总是可以实现的（不选任何元素）// 遍历每个数for (int num : nums) {// 必须从大到小遍历，防止一个数被重复使用for (int j = target; j >= num; --j) {dp[j] = dp[j] || dp[j - num];}}return dp[target]; // 是否能组成target这个和}
};