1
var minimumDifference = function (nums) {
2
  let mid = Math.floor(nums.length / 2);
3
  let firstHalf = nums.slice(0, mid),
4
    secondHalf = nums.slice(mid);
5
  let firstHalfSum = firstHalf.reduce((a, c) => a + c);
6
  let secondHalfSum = secondHalf.reduce((a, c) => a + c);
7

8
  // Find all combinations of sums of subsets made up of k integers
9
  function sumK(arr, set, idx, sum, k) {
10
    if (k === 0) return set.add(sum);
11
    if (idx === arr.length) return;
12
    sumK(arr, set, idx + 1, sum, k);
13
    sumK(arr, set, idx + 1, sum + arr[idx], k - 1);
14
  }
15

16
  function populateArray(dp, arr, isFirstArray) {
17
    for (let i = 1; i <= arr.length; i++) {
18
      let set = new Set();
19
      sumK(arr, set, 0, 0, i);
20
      set = [...set.values()];
21
      if (!isFirstArray) {
22
        // Sort the secondDP array for binary searching
23
        set.sort((a, b) => a - b);
24
      }
25
      // i === a subset of i integers
26
      dp[i] = set;
27
    }
28
  }
29

30
  let firstDP = [[0]],
31
    secondDP = [[0]];
32
  populateArray(firstDP, firstHalf, true);
33
  populateArray(secondDP, secondHalf, false);
34

35
  let min = Infinity;
36
  // i === subset of length i
37
  for (let i = 1; i < firstDP.length; i++) {
38
    for (let num1 of firstDP[i]) {
39
      let remainingNum1 = firstHalfSum - num1;
40

41
      // i + remainingSubsetLen must equal length n since our goal is to create two arrays of length n
42
      let remainingSubsetLen = secondHalf.length - i;
43

44
      let l = 0,
45
        r = secondDP[remainingSubsetLen].length - 1;
46
      while (l <= r) {
47
        let mid = l + Math.floor((r - l) / 2);
48
        let num2 = secondDP[remainingSubsetLen][mid];
49
        let remainingNum2 = secondHalfSum - num2;
50
        // arr1Sum === sum of subsets of length n and arr2Sum === sum of subsets of length n
51
        // thereby creating two arrays of length n
52
        let arr1Sum = num1 + num2,
53
          arr2Sum = remainingNum1 + remainingNum2;
54
        if (arr1Sum === arr2Sum) return 0;
55

56
        min = Math.min(min, Math.abs(arr1Sum - arr2Sum));
57
        if (arr1Sum > arr2Sum) r = mid - 1;
58
        else l = mid + 1;
59
      }
60
    }
61
  }
62
  return min;
63
};