题目

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

解答

  • 动态规划

这个解法使用了动态规划。具体来说，我们首先计算数组中所有数字的总和。如果总和是奇数，那么无法分成等和子集，直接返回 false。否则，我们就要找到一个子集，使得它的和等于总和的一半，也就是说，我们要在数组中选择一些数字，使得它们的和等于 target。

我们使用 dp 数组来记录 target 是否可以被分成等和子集。dp[i] 表示 target 为 i 时的情况，dp[i] = true 表示 target 可以被分成等和子集，否则为 false。

对于每一个数字 num，我们遍历 dp 数组的范围是 [target, num]，并且更新状态。具体来说，如果 dp[i - num] 为 true，那么 dp[i] 也为 true，因为我们可以在 dp[i - num] 的基础上加上 num 得到 dp[i]。最后，我们返回 dp[target]，判断是否可以分成等和子集。

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;
        vector<bool> dp(target + 1, false);  // 创建一个长度为target+1的vector
        dp[0] = true;  // target为0的情况是可以满足的
        for (int num : nums) {
            for (int i = target; i >= num; i--) {  // 遍历可选数字的范围是[target, num]
                dp[i] = dp[i] || dp[i - num];  // 状态转移方程
            }
        }
        return dp[target];  // 返回target是否可以被分成等和子集
    }
};

dp[i] = dp[i] || dp[i - num];是一个状态转移方程，表示当前状态 dp[i] 是否可以被满足。dp[i] 初始值为 false，如果 dp[i - num] 为 true，也就是说前面已经找到了一组数字使得它们的和等于 i - num，那么我们只需要在这个基础上再加上 num，就可以得到一组数字使得它们的和等于 i，于是我们可以将 dp[i] 设置为 true。

这里使用了逻辑或运算符（||），如果 dp[i] 本来就是 true，那么 dp[i] 的值不会改变，因为或运算符的两个操作数有一个为 true，结果就是 true。如果 dp[i - num] 为 false，那么 dp[i] 仍然是 false。