aboutsummaryrefslogtreecommitdiff
path: root/partition_arr_min_sum_diff.c
blob: 194f4f7896e81a0b6da1c50457d59c2cec3437ed (plain)
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
}