力扣416. 分割等和子集是否存在这种解法？如果存在，复杂度为多少？

Question

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

示例 1：

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

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

我的思路是：
首先将数组的所有元素相加并排序，如果最后的和是奇数就返回false因为奇数不能一分为二，如果是偶数则继续。
设数组和的一半为a，则现在的问题就是能不能用数组中的元素凑出这个a。我们首先将最大的数加入到数组b中，然后从大到小开始将数组中的元素加入到b中并计算数字和c，直到c再加一个数就大于a了，这时记d=a-c，并把前面的数都加入到数组e中。
然后开始分析前面的数，现在问题转变为从b中的元素去掉一些值，与e中的元素作交换，来看是否能凑出这个c的差值。我们可以先计算出b的第一个元素和e的每个元素的差值并记录到数组f中，将b的每个元素往后的与第一个元素的差值记录到数组g中。
现在问题转变为能否在f中选取一些数加上g中的数（一一对应，每个只能加一次）能否凑出d这个差值来，也就是从f中选取n个数，同时从g中选取n个数，来凑出d这个差值来。
我们可以采用二分查找，left为1，right为n，这样进行查找，如果对于mid，我们将从 a 中选 n 个数的和记为sum_a，从 b 中选 n 个数的和记为sum_b，需满足 sum_a + sum_b = c，可转化为 sum_a = c - sum_b。因此，解决步骤可拆解为：
计算 a 中选 n 个数的所有可能和，存入集合S_a；
计算 b 中选 n 个数的所有可能和，存入集合S_b；
检查是否存在 sum_b ∈ S_b，使得 (c - sum_b) ∈ S_a。若存在则 “能”，否则 “不能”。
对于最后这个“分别选取n个数来凑出一个目标值”这个算法我觉得这样写复杂度挺高，每次计算的量是Cn,a，在最两边复杂度低，越到中间复杂度越高，如果能找到能简化这个过程的算法，也就能以更低的复杂度来解决了。
我有一种感觉就是，我首先把这个问题转换为一个数组去凑一个数，然后又变成两个数组去凑一个数，那是否可以通过递归嵌套的方法，将这个问题不断地递归变小，直到它变得足够小就可以直接得到结果，然后就能解决问题了。

Answer 1

阿里嘎多学长整理AIGC生成，因移动端显示问题导致当前答案未能完全显示，请使用PC端查看更加详细的解答过程

力扣416. 分割等和子集是否存在这种解法？

解法：

可以使用动态规划来解决这个问题。我们可以创建一个布尔数组 dp，其中 dp[i] 表示是否可以将前 i 个数字分割成两个子集，使得两个子集的元素和相等。

复杂度：

时间复杂度为 O(n*sum)，其中 n 是数组长度，sum 是数组元素的总和。空间复杂度为 O(n)。

核心代码：

bool canPartition(int* nums, int numsSize) {
    int sum = 0;
    for (int i = 0; i < numsSize; i++) {
        sum += nums[i];
    }
    if (sum % 2 != 0) {
        return false;
    }
    int target = sum / 2;
    bool* dp = (bool*)malloc((target + 1) * sizeof(bool));
    dp[0] = true;
    for (int i = 0; i < numsSize; i++) {
        for (int j = target; j >= nums[i]; j--) {
            dp[j] = dp[j] || dp[j - nums[i]];
        }
    }
    return dp[target];
}

注意：

在上述代码中，我们首先计算数组元素的总和，如果总和为奇数，则直接返回 false，因为无法将奇数分割成两个相等的子集。然后我们创建一个布尔数组 dp，其中 dp[i] 表示是否可以将前 i 个数字分割成两个子集，使得两个子集的元素和相等。最后，我们使用动态规划的思想来填充 dp 数组，直到找到是否可以将数组分割成两个子集，使得两个子集的元素和相等。