Given a non-empty array nums 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.
Example 1:
Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.
Constraints:
1 <= nums.length <= 200
1 <= nums[i] <= 100
Solution
1. Knapsack
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for (const auto n: nums) sum += n;
if (sum % 2 != 0) return false;
const int size = nums.size() + 1, W = sum / 2 + 1;
int knapsack[size][W];
for (int w = 0; w < W; ++w) knapsack[0][w] = 0;
for (int i = 0; i < size; ++i) knapsack[i][0] = 0;
for (int i = 1; i < size; ++i) {
for (int w = 1; w < W; ++w) {
if (nums[i - 1] <= w) {
knapsack[i][w] = max(knapsack[i - 1][w], nums[i - 1] + knapsack[i - 1][w - nums[i - 1]]);
} else {
knapsack[i][w] = knapsack[i - 1][w];
}
}
}
return knapsack[size - 1][W - 1] == W - 1;
}
};
2. DP
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for (const auto n: nums) sum += n;
if (sum % 2 != 0) return false;
const int size = nums.size() + 1, S = sum / 2 + 1;
bool dp[size][S];
for (int s = 0; s < S; ++s) dp[0][s] = false;
for (int i = 0; i < size; ++i) dp[i][0] = true;
for (int i = 1; i < size; ++i) {
for (int s = 1; s < S; ++s) {
if (nums[i - 1] > s) {
dp[i][s] = false;
} else {
dp[i][s] = dp[i - 1][s] || dp[i - 1][s - nums[i - 1]];
}
}
}
return dp[size - 1][S - 1];
}
};
3. Optimized DP
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for (const auto n: nums) sum += n;
if (sum % 2 != 0) return false;
const int size = nums.size() + 1, S = sum / 2 + 1;
bool dp[S];
memset(dp, 0, S);
dp[0] = true;
for (int i = 0; i < nums.size(); ++i) {
for (int s = S - 1; s >= nums[i]; --s) {
dp[s] = dp[s] || dp[s - nums[i]];
}
}
return dp[S - 1];
}
};
