题目大意：
给你一个正整数的数组，问你能否把元素划分成元素和相等的两组。
Problem:
Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Note:
- Each of the array element will not exceed 100.
- The array size will not exceed 200.
Example 1:
|
1 2 3 4 5 |
Input: [1, 5, 11, 5] Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11]. |
Example 2:
|
1 2 3 4 5 |
Input: [1, 2, 3, 5] Output: false Explanation: The array cannot be partitioned into equal sum subsets. |
Idea:
DP 动态规划
Solution:
Time complexity: O(n*sum)
Space complexity: O(sum)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua // Running time: 16 ms class Solution { public: bool canPartition(vector<int>& nums) { const int sum = std::accumulate(nums.begin(), nums.end(), 0); if (sum % 2 != 0) return false; vector<int> dp(sum + 1, 0); dp[0] = 1; for (const int num : nums) { for (int i = sum; i >= 0; --i) if (dp[i]) dp[i + num] = 1; if (dp[sum / 2]) return true; } return false; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment