leetcode 链接：416. 分割等和子集

题目

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

示例：

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

解答 & 代码

本题可转换为 01背包问题 

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int len = nums.size();
        // 先对数组中所有元素求和
        int sum = 0;
        for(int i = 0; i < len; ++i)
            sum += nums[i];
        // 如果和为奇数，直接返回 false，不可能分为两个和相同的子集
        if(sum % 2 == 1)
            return false;
        // 将和的一半作为 01背包问题的 target
        int target = sum / 2;

        // 动态规划数组，dp[i] 代表是否存在和为 i 的组合
        vector<bool> dp(target + 1, false);
        dp[0] = true;    // 初始化，存在和为 0 的组合
        // 状态转移
        for(int i = 0; i < len; ++i)            // 外层循环遍历数组中的每个元素值 nums[i]
        {
            int val = nums[i];
            // 内层循环之所以倒序，因为dp数组是从二维优化为一维的
            // dp[j] 实际上本来是和上一行的 dp[j-val] 有关
            // 如果正序遍历 target，那么 dp[j-val] 已经是更新过的状态，而不再是上一行的 dp 值
            for(int j = target; j >= val; --j)    // 内层循环倒序遍历 target 的值
                dp[j] = dp[j] || dp[j - val];
        }
        return dp[target];
    }
};

复杂度分析：设数组长为 n

  • 时间复杂度 O(n × target)
  • 空间复杂度 O(target)

执行结果：

执行结果：通过

执行用时：84 ms, 在所有 C++ 提交中击败了 95.78% 的用户
内存消耗：9 MB, 在所有 C++ 提交中击败了 76.54% 的用户