1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
// 416. Partition Equal Subset Sum
#include "leetcode.h"
/*
* given an integer array 'nums', return true if you can partition the array
* into two subsets such that the sum of the elements in both subsets is equal
* or false otherwise
*/
bool is_subset_sum(int *nums, int numsSize, int sum) {
bool dp[numsSize + 1][numsSize + 1];
for (int i = 0; i <= numsSize; i++)
dp[i][0] = true;
for (int i = 1; i <= sum; i++)
dp[0][i] = false;
for (int i = 1; i <= numsSize; i++)
for (int j = 1; j <= sum; j++)
dp[i][j] = nums[i - 1] <= j ? dp[i - 1][j - nums[i - 1]] || dp[i - 1][j]
: dp[i - 1][j];
return dp[numsSize][sum];
}
bool canPartition(int *nums, int numsSize) {
int sum = 0;
for (int i = 0; i < numsSize; i++)
sum += nums[i];
if ((sum % 2))
return false;
return is_subset_sum(nums, numsSize, sum / 2);
}
int main() {
int n1[] = {1, 5, 11, 5}, n2[] = {1, 2, 3, 5};
printf("%d\n", canPartition(n1, ARRAY_SIZE(n1))); // expect: 1
printf("%d\n", canPartition(n2, ARRAY_SIZE(n2))); // expect: 0
}
|