1
class Solution {
2
  public int minimumDifference(int[] nums) {
3
    int n = nums.length;
4
    int sum = 0;
5
    for (int i : nums) {
6
      sum += i;
7
    }
8

9
    TreeSet<Integer>[] sets = new TreeSet[n / 2 + 1];
10
    for (int i = 0; i < (1 << (n / 2)); ++i) {
11
      int curSum = 0;
12
      int m = 0;
13
      for (int j = 0; j < n / 2; ++j) {
14
        if ((i & (1 << j)) != 0) {
15
          curSum += nums[j];
16
          m++;
17
        }
18
      }
19
      if (sets[m] == null) sets[m] = new TreeSet<Integer>();
20
      sets[m].add(curSum);
21
    }
22

23
    int res = Integer.MAX_VALUE / 3;
24
    for (int i = 0; i < (1 << (n / 2)); ++i) {
25
      int curSum = 0;
26
      int m = 0;
27
      for (int j = 0; j < n / 2; ++j) {
28
        if ((i & (1 << j)) != 0) {
29
          curSum += nums[n / 2 + j];
30
          m++;
31
        }
32
      }
33
      int target = (sum - 2 * curSum) / 2;
34

35
      Integer left = sets[n / 2 - m].floor(target), right = sets[n / 2 - m].ceiling(target);
36
      if (left != null) {
37
        res = Math.min(res, Math.abs(sum - 2 * (curSum + left.intValue())));
38
      }
39

40
      if (right != null) {
41
        res = Math.min(res, Math.abs(sum - 2 * (curSum + right.intValue())));
42
      }
43

44
      if (res == 0) return 0;
45
    }
46

47
    return res;
48
  }
49
}
50
// Time Complexity: O(2^(n/2) * n/2 * n/2)