416. To divide into equal and subsets

One 、 subject

Original link ：416. To divide into equal and subsets

1. Title Description

To give you one Contains only positive integers Of Non empty Array nums . Please decide whether you can divide this array into two subsets , Make the sum of the elements of the two subsets equal .

Example 1：

 Input ：nums = [1,5,11,5]
 Output ：true
 explain ： Arrays can be divided into  [1, 5, 5]  and  [11] .

Example 2：

 Input ：nums = [1,2,3,5]
 Output ：false
 explain ： An array cannot be divided into two elements and equal subsets .

Tips ：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

2. Basic framework

C++ The basic framework code is as follows :

bool canPartition(vector<int>& nums) {
    
}

3. Their thinking

• Topic analysis

1. The goal of the question is to determine whether the array can be divided into two subsets , It can be for true, Otherwise false.
2. The elements in these two subsets can be discontinuous , So we can't solve the problem by prefix and .
3. We have to try our best to prove that it has two subsets of elements and is equal .
4. First of all, will nums Sum the elements of the array , by sum. As long as it is proved that the sum of elements in the set is sum / 2 The combination of , It means nums An array can be divided into two elements and equal subsets .
5. If sum % 2 == 1, Note that there are no two elements and the same subset , return false.
6. Each element can only be taken once .
7. Come here , You will find , Follow 01 The solution of knapsack problem is the same , Each element value is equivalent to 01 Items in the backpack , And can only be taken once ,01 The capacity in the backpack is target, Here it is sum / 2, Put these two elements into 01 Just solve the knapsack formula .

• Implementation code ：

  bool canPartition(vector<int>& nums) {
        
      int sum = 0; 
      for (int i = 0; i < nums.size(); i++)
          sum += nums[i];
      if (sum % 2 == 1) return false;
      int target = sum / 2; //  amount to 01 Capacity in backpack 
      memset(dp, 0, sizeof(dp));
      for (int i = 0; i < nums.size(); i++)        
          for (int j = target; j >= nums[i]; j--)
              dp[j] = max(dp[j], dp[ j - nums[i] ] + nums[i]);
      if (target == dp[target]) // This indicates that the sum of the elements in the set is target
          return true;
      return false;
  }