Log inSign up
hardGeeksforGeeksNot Started

Tug of War

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Backtracking
Solve on GeeksforGeeks
Lesson

Problem Statement

Given a set of n integers, divide the array into two subsets of sizes n/2 and (n - n/2) respectively such that the difference between the sum of elements in both subsets is as small as possible.

If n is even, both subsets must have size n/2. If n is odd, one subset has size (n - 1)/2 and the other has size (n + 1)/2.

Example 1:

Input: arr = [3, 4, 5, -3, 100, 1, 89, 54, 23, 20]
Output: Subset 1: [4, -3, 5, 1, 89], Subset 2: [3, 100, 54, 23, 20]
Explanation: Sum of Subset 1 = 96, Sum of Subset 2 = 200, Difference = 104 (optimal minimum).

Example 2:

Input: arr = [23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4]
Output: Subset 1: [45, -34, 12, 98, -1], Subset 2: [23, 0, -99, 4, 189, 4]
Explanation: Both subsets achieve minimum possible sum difference with sizes 5 and 6.

Constraints:

  • 1 <= n <= 30
  • -1000 <= arr[i] <= 1000

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master lookahead size pruning for fixed-size subset selection: currSelected + (n - currIdx) >= reqSize.
  • Formulate subset partition problems in terms of totalSum - 2 * currSum.
  • Understand the difference between unconstrained partition (0/1 Knapsack DP) vs exact equal-size partition (Tug of War).

1. Combinations Generator with Set Difference

Intuition

Iterate recursively to select N/2 indices. Compute the sum of selected elements and compare with remaining elements.

Algorithm

  1. Step 1: Generate all 2N subsets of the array.
  2. Step 2: Filter to keep only subsets of exact size N/2 (or (N-1)/2 if N is odd).
  3. Step 3: For each subset, calculate abs(totalSum - 2 * subsetSum).
  4. Step 4: Track and return the two subsets that yield the minimum difference.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <cmath>
4#include <climits>
5#include <numeric>
6
7class Solution {
8public:
9 void backtrack(int start, const std::vector<int>& arr, int k, std::vector<int>& current, int totalSum, int& minDiff, std::vector<int>& bestSet) {
10 if ((int)current.size() == k) {
11 int currentSum = 0;
12 for (int x : current) currentSum += x;
13 int diff = std::abs(totalSum - 2 * currentSum);
14 if (diff < minDiff) {
15 minDiff = diff;
16 bestSet = current;
17 }
18 return;
19 }
20 for (int i = start; i < (int)arr.size(); i++) {
21 current.push_back(arr[i]);
22 backtrack(i + 1, arr, k, current, totalSum, minDiff, bestSet);
23 current.pop_back();
24 }
25 }
26
27 std::pair<std::vector<int>, std::vector<int>> tugOfWar(const std::vector<int>& arr) {
28 int n = arr.size();
29 int totalSum = std::accumulate(arr.begin(), arr.end(), 0);
30 int k = n / 2;
31 int minDiff = INT_MAX;
32 std::vector<int> current, bestSet;
33
34 backtrack(0, arr, k, current, totalSum, minDiff, bestSet);
35
36 std::vector<int> otherSet;
37 std::vector<bool> used(n, false);
38 for (int x : bestSet) {
39 for (int i = 0; i < n; i++) {
40 if (!used[i] && arr[i] == x) {
41 used[i] = true;
42 break;
43 }
44 }
45 }
46 for (int i = 0; i < n; i++) {
47 if (!used[i]) otherSet.push_back(arr[i]);
48 }
49 return {bestSet, otherSet};
50 }
51};
52
53int main() {
54 Solution solver;
55 std::vector<int> arr = {3, 4, 5, -3, 100, 1, 89, 54, 23, 20};
56 auto [s1, s2] = solver.tugOfWar(arr);
57 std::cout << "Subset 1 size: " << s1.size() << "\n";
58 std::cout << "Subset 2 size: " << s2.size() << "\n";
59 return 0;
60}

Time & Space Complexity

  • Time complexity: O(N * C(N, N/2)) — Generates C(N, N/2) combinations, taking O(N) to process each.
  • Space complexity: O(N) — O(N) for current combination buffer and call stack.

2. Branch & Bound Include/Exclude Backtracking

Intuition

Track currElements and currSum. If currElements + (n - currIdx) < n/2 or currElements > n/2, prune the branch immediately.

When to apply: Recursive backtracking with subset size and remaining element pruning.

Algorithm

  1. Step 1: Define solve(index, selectedCount, currentSum).
  2. Step 2: Branch 1 (Include): If selectedCount < n/2, include arr[index], recurse with selectedCount + 1.
  3. Step 3: Branch 2 (Exclude): If (n - 1 - index) >= (n/2 - selectedCount), recurse without arr[index].
  4. Step 4: When selectedCount == n/2, update minimum difference minDiff = min(minDiff, abs(totalSum - 2 * currentSum)).
  5. Step 5: Record the best partition configuration.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <cmath>
4#include <climits>
5#include <numeric>
6
7class Solution {
8public:
9 void solve(const std::vector<int>& arr, int currIdx, int currElements, int currSum, int totalSum, int n, int k, std::vector<bool>& currIncluded, int& minDiff, std::vector<bool>& bestIncluded) {
10 if (currElements == k) {
11 int diff = std::abs(totalSum - 2 * currSum);
12 if (diff < minDiff) {
13 minDiff = diff;
14 bestIncluded = currIncluded;
15 }
16 return;
17 }
18 if (currIdx == n) return;
19 if (currElements + (n - currIdx) < k) return; // Cannot form size k
20
21 // Choice 1: Include arr[currIdx]
22 currIncluded[currIdx] = true;
23 solve(arr, currIdx + 1, currElements + 1, currSum + arr[currIdx], totalSum, n, k, currIncluded, minDiff, bestIncluded);
24 currIncluded[currIdx] = false;
25
26 // Choice 2: Exclude arr[currIdx]
27 solve(arr, currIdx + 1, currElements, currSum, totalSum, n, k, currIncluded, minDiff, bestIncluded);
28 }
29
30 std::pair<std::vector<int>, std::vector<int>> tugOfWar(const std::vector<int>& arr) {
31 int n = arr.size();
32 int totalSum = std::accumulate(arr.begin(), arr.end(), 0);
33 int k = n / 2;
34 int minDiff = INT_MAX;
35 std::vector<bool> currIncluded(n, false), bestIncluded(n, false);
36
37 solve(arr, 0, 0, 0, totalSum, n, k, currIncluded, minDiff, bestIncluded);
38
39 std::vector<int> s1, s2;
40 for (int i = 0; i < n; i++) {
41 if (bestIncluded[i]) s1.push_back(arr[i]);
42 else s2.push_back(arr[i]);
43 }
44 return {s1, s2};
45 }
46};
47
48int main() {
49 Solution solver;
50 std::vector<int> arr = {3, 4, 5, -3, 100, 1, 89, 54, 23, 20};
51 auto [s1, s2] = solver.tugOfWar(arr);
52 std::cout << "S1 size: " << s1.size() << ", S2 size: " << s2.size() << "\n";
53 return 0;
54}

Time & Space Complexity

  • Time complexity: O(C(N, N/2)) — Pruned binary decision tree with lookahead bounds.
  • Space complexity: O(N) — O(N) boolean tracking array.

3. Optimized Backtracking with Early Zero-Difference Termination (Gold Standard)

Intuition

Tracks the minimal difference using binary include/exclude decisions. The moment minDiff == 0 is achieved, further recursive branching returns immediately since difference 0 is globally optimal.

Algorithm

  1. Step 1: Sort arr in descending order upfront to place larger numbers first and enable tighter bound checks.
  2. Step 2: Maintain totalSum = sum(arr), targetSize = N / 2.
  3. Step 3: In solve(currIdx, selectedCount, currSum): prune if selectedCount + (N - currIdx) < targetSize (insufficient elements left).
  4. Step 4: Prune if selectedCount > targetSize.
  5. Step 5: If selectedCount == targetSize, compute diff = abs(totalSum - 2 * currSum); if diff < minDiff, update best partition.
  6. Step 6: If diff == 0, terminate search immediately (perfect balanced split found).

Tug of War Partition Trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Calculate totalSum = 296, targetSize = 5
Visual state
Values and pointers at this exact step
tree
Root
sel: 0, sum: 0

Node order shown; add connections to display explicit tree edges.

Variables at this step
index
0
selectedCount
0
currentSum
0
minDiff
null
Check / comparison
totalSum = 296, targetSize = 5, minDiff = INFINITY
Decision / next transition
Explore inclusion / exclusion branches
Why this step matters

Calculate totalSum = 296, targetSize = 5. Start at index 0 with selectedCount = 0, currentSum = 0.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <cmath>
4#include <climits>
5#include <numeric>
6
7class Solution {
8public:
9 bool solve(const std::vector<int>& arr, int currIdx, int currElements, int currSum, int totalSum, int n, int k, std::vector<bool>& currIncluded, int& minDiff, std::vector<bool>& bestIncluded) {
10 if (currElements == k) {
11 int diff = std::abs(totalSum - 2 * currSum);
12 if (diff < minDiff) {
13 minDiff = diff;
14 bestIncluded = currIncluded;
15 }
16 return minDiff == 0; // Early exit if exact split found
17 }
18 if (currIdx == n || currElements + (n - currIdx) < k) return false;
19
20 // Include
21 currIncluded[currIdx] = true;
22 if (solve(arr, currIdx + 1, currElements + 1, currSum + arr[currIdx], totalSum, n, k, currIncluded, minDiff, bestIncluded)) {
23 return true;
24 }
25 currIncluded[currIdx] = false;
26
27 // Exclude
28 if (solve(arr, currIdx + 1, currElements, currSum, totalSum, n, k, currIncluded, minDiff, bestIncluded)) {
29 return true;
30 }
31 return false;
32 }
33
34 std::pair<std::vector<int>, std::vector<int>> tugOfWar(const std::vector<int>& arr) {
35 int n = arr.size();
36 int totalSum = std::accumulate(arr.begin(), arr.end(), 0);
37 int k = n / 2;
38 int minDiff = INT_MAX;
39 std::vector<bool> currIncluded(n, false), bestIncluded(n, false);
40
41 solve(arr, 0, 0, 0, totalSum, n, k, currIncluded, minDiff, bestIncluded);
42
43 std::vector<int> s1, s2;
44 for (int i = 0; i < n; i++) {
45 if (bestIncluded[i]) s1.push_back(arr[i]);
46 else s2.push_back(arr[i]);
47 }
48 return {s1, s2};
49 }
50};
51
52int main() {
53 Solution solver;
54 std::vector<int> arr = {3, 4, 5, -3, 100, 1, 89, 54, 23, 20};
55 auto [s1, s2] = solver.tugOfWar(arr);
56 std::cout << "Optimal Tug of War Solution:\n";
57 std::cout << "Subset 1: ";
58 for (int x : s1) std::cout << x << " ";
59 std::cout << "\nSubset 2: ";
60 for (int x : s2) std::cout << x << " ";
61 std::cout << "\n";
62 return 0;
63}

Time & Space Complexity

  • Time complexity: O(C(N, N/2)) — Explores combinations with early exit on exact subset sum match.
  • Space complexity: O(N) — O(N) recursion stack depth.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Generate All Combinations C(N, N/2)O(C(N, N/2))O(N)Generate every combination of size N/2 and compute difference with complement sum.Combinatorial state exploration
2.Branch & Bound Include/Exclude Backtracking (Better)O(C(N, N/2))O(N)Include / Exclude recursion with remaining element count lookahead.Search space depth
3.Optimized Backtracking with Best-State Snapshot (Optimal)OptimalO(C(N, N/2))O(N)Pruned backtracking that immediately updates best boolean masks and terminates branches at target sum 0.Combinations of size N/2

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Forgetting that subset sizes must be strictly equal (or differ by at most 1 for odd N), confusing it with standard unconstrained partition problem.

Pitfall 2:

Continuing to recurse even when remaining elements in array cannot satisfy the required subset size.

Crucial Edge Cases to Validate:

  • Even N (e.g. 4 elements) -> splits into sizes 2 and 2.
  • Odd N (e.g. 5 elements) -> splits into sizes 2 and 3.
  • Array with negative numbers (e.g. [-3, 100, -5]) -> correctly handles signed sums and absolute difference.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify how the problem differs from Partition Equal Subset Sum (equal cardinality vs arbitrary cardinality).
  2. Explain the lookahead pruning check currElements + (n - currIdx) >= k to show proactive branch pruning.
  3. Mention how returning early when diff == 0 drastically speeds up cases where a perfect split exists.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is Tug of War strictly constrained to C(N, N/2) search space rather than 2N?

Back to DSA Sheet