Tug of War | Problems

Given a set of n integers, divide the set in two subsets of n/2 sizes each such that the difference of the sum of two subsets is as minimum as possible. If n is even, then sizes of both subsets must be n/2. If n is odd, then one subset should be (n-1)/2 and other should be (n+1)/2.

Sample Input

[3, 4, 5, -3, 100, 1, 89, 54, 23, 20]

Sample Output

Subsets with minimum difference

Constraints

1 <= n <= 20
-10^6 <= arr[i] <= 10^6

Topics

Backtracking Recursion

Each element can belong to either subset. Use backtracking to explore all partitions of size n/2 and track the minimum absolute difference between the two subset sums.

function tugOfWar(arr) {
  const n = arr.length;
  const half = Math.floor(n / 2);
  const totalSum = arr.reduce((a, b) => a + b, 0);
  let minDiff = Infinity;
  let bestSubset = [];

  function backtrack(idx, count, currentSum, chosen) {
    if (count === half) {
      const diff = Math.abs(totalSum - 2 * currentSum);
      if (diff < minDiff) {
        minDiff = diff;
        bestSubset = [...chosen];
      }
      return;
    }
    if (idx >= n || n - idx < half - count) return;

    chosen.push(arr[idx]);
    backtrack(idx + 1, count + 1, currentSum + arr[idx], chosen);
    chosen.pop();
    backtrack(idx + 1, count, currentSum, chosen);
  }

  backtrack(0, 0, 0, []);
  return { minDiff, bestSubset };
}

Time: O(2^n) Space: O(n)

Saved in this browser only. Private to you.