leetcode416：分割等和子集

题目链接

leetcode

题目描述

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

C++ 代码

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

/*
    对集合求和得到 sum，然后把问题转化为背包问题。
    给一个容量为 sum/2 的背包和 N 个物品，每个物品的容量为 nums[i]。
    现在装物品，是否存在一种方法，可以恰好将背包装满？

    状态定义：
        dp[i][j] 表示前 i 个物品，使用 j 容量的背包，是否可以恰好装满。
    状态转移：
        第 i 个物品不装入背包
            dp[i][j] = dp[i-1][j]
        第 i 个物品装入背包
            dp[i][j] = dp[i-1][j-nums[i-1]]

    时间复杂度：O(nm)
        n 表示数组的长度，m 表示容量大小。
    空间复杂度：O(nm)
*/
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        // 和为奇数，不能分割成两个等和子集
        if (sum % 2 != 0) {
            return false;
        }

        int n = nums.size();
        int target = sum/2;
        vector<vector<bool>> f(n+1, vector<bool>(target+1, false));
        // 初始化
        for (int i = 0; i <= n; i++) {
            f[i][0] = true;
        }

        // 状态计算
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= target; j++) {
                if (j - nums[i-1] < 0) {
                    // 背包容量不足，不能装入该物品
                    f[i][j] = f[i-1][j];
                } else {
                    // 不装入，或者装入
                    f[i][j] = f[i-1][j] || f[i-1][j-nums[i-1]];
                }
            }
        }

        return f[n][target];
    }
};

/*
    优化空间

    时间复杂度：O(nm)
    空间复杂度：O(m)
*/
class Solution_1 {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        // 和为奇数，不能分割成两个等和子集
        if (sum % 2 != 0) {
            return false;
        }

        int n = nums.size();
        int target = sum/2;
        vector<bool> f(target+1, false);
        // 初始化
        f[0] = true;

        // 状态计算
        for (int i = 1; i <= n; i++) {
            for (int j = target; j >= nums[i-1]; j--) {
                // 不装入，或者装入
                f[j] = f[j] || f[j-nums[i-1]];
            }
        }

        return f[target];
    }
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

int main() {
    Solution solution;
    vector<vector<int>> nums_cases = {
        {1,5,11,5},
        {1,2,3,5}
    };

    for (auto& nums : nums_cases) {
        cout << "Input: nums = ";
        printArray(nums);
        cout << endl;
        bool result = solution.canPartition(nums);
        cout << "Output: " << (result ? "true" : "false") << endl;
    }

    return 0;
}