Tug of War Editorial

Practice Problem Link: Tug of War

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a set of n integers denoting the strength of each student participating in a tug of war, divide the students into 2 equal parts such that the difference between the strengths of both the groups is minimum. Return the difference between the strengths of both the groups.

Note: If the number of students is odd, one group will have an extra student.

Approach

• The idea is to make a single team of half the number of students by trying every possible combination. And the remaining students will be in the other team.
• Keep the track of the sum of the strengths of the selected students.
• If the minimum difference of the strengths of the two teams is less than the minimum difference obtained so far then update the minimum difference.

Analysis

• Time Complexity: O(2n)
• Auxiliary Space Complexity: O(1)

Implementation

C++

int minDiff;
void getPartition(vector<int> &A, int selectedStudents, int start, int currSum, int totalSum) {
	if (start == A.size()) {
		return;
	}
	if (selectedStudents == A.size()/2) {
		minDiff = min(minDiff, abs(totalSum - 2 * currSum));
		return;
	}
	getPartition(A, selectedStudents + 1, start + 1, currSum + A[start], totalSum);
	getPartition(A, selectedStudents, start + 1, currSum, totalSum);
}
int divideGroup(vector<int> &A) {
	int totalSum = 0;
	for (int i = 0; i < A.size(); i++) {
		totalSum += A[i];
	}
	minDiff = INT_MAX;
	getPartition(A, 0, 0, 0, totalSum);
	return minDiff;
}

Java

class Solution {
	static int minDiff;
	void getPartition(int[] A, int selectedStudents, int start, int currSum, int totalSum) {
		if (start == A.length) {
			return;
		}
		if (selectedStudents == A.length/2) {
			minDiff = Math.min(minDiff, Math.abs(totalSum - 2 * currSum));
			return;
		}
		getPartition(A, selectedStudents + 1, start + 1, currSum + A[start], totalSum);
		getPartition(A, selectedStudents, start + 1, currSum, totalSum);
	}
	int divideGroup(int[] A) {
	    int totalSum = 0;
		for (int i = 0; i < A.length; i++) {
			totalSum += A[i];
		}
		minDiff = Integer.MAX_VALUE;
		getPartition(A, 0, 0, 0, totalSum);
		return minDiff;
	}
}