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
Daily Recommendation