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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
// 2035. Partition Array Into Two Arrays to Minimize Sum Difference
#include "leetcode.h"
/*
* you are given an integer array 'nums' of '2 * n' integers. you need to
* partition 'nums' into two arrays of length 'n' to minimise the abresute
* difference of sums of the arrays. to partition 'nums', put each element of
* 'nums' into one of the two arrays. return the minimum possible abresute
* difference
*/
#define MAX_SN 7000
int sum_array(int *arr, int n) {
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
return sum;
}
int cmp(const void *a, const void *b) {
return *(const int *)a - *(const int *)b;
}
void list_subset(int subset[16][MAX_SN], int subset_size[16], int *nums, int n,
int partial_sum, int m) {
if (!n) {
subset[m][subset_size[m]++] = partial_sum;
return;
}
list_subset(subset, subset_size, nums + 1, n - 1, partial_sum, m);
list_subset(subset, subset_size, nums + 1, n - 1, partial_sum + nums[0],
m + 1);
}
void mim(int subset[16][MAX_SN], int subset_size[16], int *nums, int n,
int partial_sum, int m, int *res, int total, int nn,
int memo[16][11939]) {
if (!n) {
if (memo[m][abs(partial_sum + 11939) % 11939])
return;
memo[m][abs(partial_sum + 11939) % 11939] = 1;
int l, r, mid, tmp, comp_size;
comp_size = nn / 2 - m;
l = 0;
r = subset_size[comp_size] - 1;
tmp = abs(total - 2 * (subset[comp_size][r] + partial_sum));
if (!r || abs(total - 2 * (subset[comp_size][r] + partial_sum)) > tmp) {
*res = fmin(*res, tmp);
return;
}
tmp = abs(total - 2 * (subset[comp_size][l] + partial_sum));
if (abs(total - 2 * (subset[comp_size][l + 1] + partial_sum)) > tmp) {
*res = fmin(*res, tmp);
return;
}
while (r - l > 3) {
mid = l + (r - l) / 2;
tmp = abs(total - 2 * (subset[comp_size][mid] + partial_sum));
if (abs(total - 2 * (subset[comp_size][mid + 1] + partial_sum)) > tmp)
r = mid;
else if (abs(total - 2 * (subset[comp_size][mid + 1] + partial_sum)) <
tmp)
l = mid;
else
r--;
}
for (int i = l; i <= r; ++i) {
tmp = abs(total - 2 * (subset[comp_size][i] + partial_sum));
*res = fmin(*res, tmp);
}
} else {
mim(subset, subset_size, nums + 1, n - 1, partial_sum, m, res, total, nn,
memo);
mim(subset, subset_size, nums + 1, n - 1, partial_sum + nums[0], m + 1, res,
total, n, memo);
}
}
int minimumDifference(int *nums, int numsSize) {
int total = sum_array(nums, numsSize), ans = INT_MAX, subset[16][MAX_SN],
subset_size[16] = {0}, memo[16][11939];
list_subset(subset, subset_size, nums, numsSize / 2, 0, 0);
for (int i = 0; i <= numsSize / 2; ++i)
qsort(subset[i], subset_size[i], sizeof(subset[i][0]), cmp);
mim(subset, subset_size, nums + numsSize / 2, numsSize / 2, 0, 0, &ans, total,
numsSize, memo);
return ans;
}
int main() {
int n1[] = {3, 9, 7, 3}, n2[] = {-36, 36}, n3[] = {2, -1, 0, 4, -2, -9};
printf("%d\n", minimumDifference(n1, ARRAY_SIZE(n1))); // expect: 2
printf("%d\n", minimumDifference(n2, ARRAY_SIZE(n2))); // expect: 72
printf("%d\n", minimumDifference(n3, ARRAY_SIZE(n3))); // expect: 0
}
|