分割等和子集

描述

给你一个 只包含正整数 的 非空 数组 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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/partition-equal-subset-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

题目要求将给定的数组分成两个子集，使得这两个子集的元素和相等。因此，我们可以先计算出数组元素的和 sum，如果 sum 为奇数，那么无法分成两个元素和相等的子集，直接返回 false。

接着，我们需要求出一个目标值 target，使得数组的一个子集的元素和等于 target。由于数组元素的和为 sum，因此，如果 sum 是偶数，那么我们可以将其分成两个元素和相等的子集，即 target = sum / 2。

接下来，我们可以使用动态规划来解决此问题。定义 dp[i] 表示能否组成和为 i 的子集。初始状态为 dp[0] = true，表示可以组成和为 0 的子集。对于数组中的每个元素 num，我们需要从大到小枚举 i，更新 dp[i] 的值。具体来说，如果 dp[i - num] 为 true，那么 dp[i] 也为 true。

最后，我们只需要返回 dp[target] 的值即可。

时间复杂度分析：该算法的时间复杂度为 O(n * target)，其中 n 是数组的长度，target 是数组元素的和的一半。空间复杂度为 O(target)。

C++代码

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);  // 计算数组元素的和
        if (sum % 2 != 0) {  // 如果和为奇数，返回 false
            return false;
        }
        int target = sum / 2;  // 计算目标值，即数组元素和的一半
        vector<bool> dp(target + 1, false);  // dp[i] 表示能否组成和为 i 的子集
        dp[0] = true;  // 初始状态，可以组成和为 0 的子集
        for (int num : nums) {
            for (int i = target; i >= num; i--) {  // 从大到小枚举 i
                dp[i] = dp[i] || dp[i - num];  // 转移方程
            }
        }
        return dp[target];  // 返回 dp[target]
    }
};