Leetcode 416. 分割等和子集 C++_c语言是否可以将这个数组分割成两个子集

Leetcode 416. 分割等和子集

题目

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

注意:

1. 每个数组中的元素不会超过 100
2. 数组的大小不会超过 200

测试样例

示例 1:

输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].
1
2
3
4
5

示例 2:

输入: [1, 2, 3, 5]

输出: false

解释: 数组不能分割成两个元素和相等的子集.
1
2
3
4
5

题解

根据题意可以知道，如果数组的和为sum，那么最终我们需要分为两个和为sum/2的子集。显然，和需要为偶数。另外，我们只要找到一个子数组，其数组和为sum/2即可，这样剩下的数的和肯定是sum/2
动态规划
令dp[i][j]表示前i个数是否可以组合成一个和为j的数组。那么对于nums[i-1]我们可以选它，也可以不选它，选它的话就是dp[i][j] = dp[i-1][j-nums[i]，不选它的话就是dp[i][j] = dp[i-1][j]
详细过程见代码

代码

bool canPartition(vector<int>& nums) {
        int sum=0,n=nums.size();
        for(int i=0; i<n; i++)
            sum += nums[i];
        if(sum % 2 != 0)    return false;
        else sum /= 2;
        vector<vector<bool>> dp(n+1,vector(sum+1,false));
        for(int i=0; i<=n;  i++)
            dp[i][0] = true;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=sum; j++){
                dp[i][j] = dp[i-1][j];
                if(j >= nums[i-1])    dp[i][j] = dp[i][j] || dp[i-1][j - nums[i-1]];
            }
                
        }
        return dp[n][sum];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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