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,
switch Statement programming : Give a percentage score , Output grade required A,B,C,D,E.Jetson Nano read GPS data (TTL turn USB)yolov3 Detailed explanation - model structure Android Mobile application foundation learning —— Chapter 1 basic introduction Four years of programming , Or is it inferior Database design AWS Elastic Load Balancing (Amazon ELB) Study notes el-select Parameter problem From outsourcing testing to Alibaba , A girl of three books C++STL Container summary