Tug of War Hard 0 attempts
GeeksforGeeks ↗

Tug of War

Hard BacktrackingRecursion GeeksforGeeks

Split a set of n integers into two groups so that the gap between their sums is as small as it can possibly be, under a fixed sizing rule: when n is even, both groups must contain exactly n/2 elements; when n is odd, one group gets (n-1)/2 elements and the other gets (n+1)/2.

Input Format
Implement tugOfWar(arr). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement. Any result satisfying the statement is accepted.

Sample Input and Output

Example 1 ยท Run Sample

Input
arr = [1,2,3,4]
Output
{"minDiff":0,"bestSubset":[1,4]}

Example 2

Input
arr = [1]
Output
{"minDiff":1,"bestSubset":[]}
Constraints
  • 1 <= n <= 20
  • -10^6 <= arr[i] <= 10^6
Test Cases (2)
Case 1
Args: [[1,2,3,4]] Expected: {"minDiff":0,"bestSubset":[1,4]}
Case 2
Args: [[1]] Expected: {"minDiff":1,"bestSubset":[]}
Topics
BacktrackingRecursion

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.

javascript
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.

JavaScript