416. 分割等和子集

难度中等218

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

注意:

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

示例 1:

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

输出: true

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

示例 2:

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

输出: false

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

01背包问题 具体解体思路见注释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        //背包问题
        //背包的容量是总和的一半
        //dp[i][j] 表示取了前i个数剩余容积为j时候的最大值
        //dp[i][j]=max(dp[i-1][j],dp[i-1][j-num[i]]+num[i])

        int sum=0;
        int n=nums.size();
        for(int i=0;i<n;i++){
            sum+=nums[i];
        }
        if(sum%2!=0){
            return false;
        }

        int V=sum/2;
        vector<vector <int> > dp(n,vector<int>(V+1,0));

        //初始化:
        dp[0][0]=0;
        //只取0号数字的时候的初始化：
        for(int i=nums[0];i<=V;i++){//注意越界问题
            dp[0][i]=nums[0];//因为只能取一次nums[0];
            }
        //dp状态转移
        for(int i=1;i<n;i++){
            for(int j=0;j<=V;j++){
                
                if(j-nums[i]>=0)
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i]);
                else{
                    dp[i][j]=dp[i-1][j];
                }
            }
        }

        if(dp[n-1][V]!=V){
            return false;
        }
        return true;



    }
};