416. Dividing equal sum subsets

Given a non empty array containing only positive integers . Can I split this array into two subsets , Make the sum of elements of two subsets equal .

be careful :

The number of elements in each array will not exceed 100
The size of the array will not exceed 200
Examples 1:

input :
[1, 5, 11, 5]
output :
true
explain : Arrays can be split into [1, 5, 5] and [11].

Examples 2:

input :
[1, 2, 3, 5]
output :
false
explain : An array cannot be split into two elements and an equal subset .

thinking :

First judge whether the total number is even , Determine Backpack Capacity , Then traverse to determine whether the backpack capacity is large enough , If it is not large enough, the current state depends on the previous state , Large enough will reduce the backpack capacity , Put the element in the backpack , Judge the state again .

code :
class Solution { public: bool canPartition(vector<int> &nums) { int tar = 0, n
= nums.size(); for (int i = 0; i < n; i++) tar += nums[i]; if (tar % 2 != 0)
// Judge whether the sum is even return false; tar /= 2; // Sum of each subset vector<bool> dp(tar + 1, false); dp
[0] = true; //database for (int i = 0; i < n; i++) { for (int j = tar; j >= 0; j
--) // reverse traversal , Ensure that each element is used only once { if (j - nums[i] >= 0) { dp[j] = dp[j] || dp[j - nums[i]
]; } } } return dp[tar]; } };

Technology
©2019-2020 Toolsou All rights reserved,
VUE+Canvas Achieve desktop Pinball brick elimination games C/C++ Memory model 2019PHP Interview questions ( Continuously updated )PHPspringboot2 Separation of front and rear platforms ,token Put in header Pit for verification Vue SpringBoot conduct Excel download element-ui Step on pit record 45 The 12-year-old programmer was turned down , Is the workplace wrong ?Python Web frame Pandas Fundamentals of statistical analysis _ data processing (DataFrame Common operations )Java Misunderstanding —— Method overloading is a manifestation of polymorphism ?