1
class Solution {
2
 public:
3
  int minimumDifference(vector<int> &nums) {
4
    int n = nums.size() / 2;
5
    vector<int> left(nums.begin(), nums.begin() + n), right(nums.begin() + n, nums.begin() + 2 * n);
6

7
    vector<vector<int>> vals(n + 1);
8
    for (int mask = 0; mask < (1 << n); ++mask) {
9
      int diff = 0, key = __builtin_popcount(mask);
10
      for (int i = 0; i < n; ++i) diff += (mask & (1 << i)) ? left[i] : -left[i];
11
      vals[key].push_back(diff);
12
    }
13

14
    for (auto &v : vals) sort(v.begin(), v.end());
15

16
    int ans = INT_MAX;
17
    for (int mask = 0; mask < (1 << n); ++mask) {
18
      int diff = 0, key = n - __builtin_popcount(mask);
19
      for (int i = 0; i < n; ++i) diff += (mask & (1 << i)) ? right[i] : -right[i];
20
      auto it = lower_bound(vals[key].begin(), vals[key].end(), -diff);
21
      if (it != vals[key].begin()) ans = min(ans, abs(diff + *prev(it)));
22
      if (it != vals[key].end()) ans = min(ans, abs(diff + *it));
23
    }
24
    return ans;
25
  }
26
};