295. Tug of War

Given an array of n integers, divide all of them into two subsets such that the subset sizes differ by at most 1 (if n is even, both subsets have n/2 elements; if n is odd, one has floor(n/2) and the other ceil(n/2)) and the absolute difference between the two subsets' sums is as small as possible. Print that minimum possible difference.

Input: The first line contains an integer n. The second line contains n space-separated integers, which may be negative. Output: Print a single integer - the minimum possible absolute difference between the two subset sums.

1 <= n <= 20, -1000 <= arr[i] <= 1000

Negative values are explicitly allowed in this problem's constraints - the backtracking approach handles this naturally, since it's just tracking sums and counts directly, unlike some DP-based subset-sum techniques that assume non-negative values for indexing purposes.

Split an array into two subsets of nearly equal size, minimizing the difference between their sums. Brute force: Try every possible way to split the array into two groups of the required sizes directly (choosing which elements go in the first group) - this is what the backtracking approach does, but WITHOUT the eager pruning it would explore many clearly-doomed branches (like continuing to add elements to a subset that's already reached its target size). Optimised: Pruning branches the moment they've EITHER reached the target subset size OR can no longer possibly reach it (too few elements remain) significantly cuts down the search space compared to blindly trying every include/exclude combination - though the underlying complexity remains exponential in the worst case, given the small constraint (n<=20).

Recursively decide, for each element in turn, whether to place it in the first subset or the second, maintaining the running count and sum of the first subset so far, and immediately abandon a branch as soon as the first subset's count would exceed the allowed size or as soon as the remaining unplaced elements couldn't possibly fill it to the required size. Once all elements are placed in a complete, valid-size split, compute the sum difference and track the minimum. This search tree is much smaller than the full 2^n subsets because entire invalid-size branches are cut early, though it remains exponential in the worst case. Time: O(C(n, n/2)) leaf evaluations, worst case still exponential Space: O(n) recursion depth

Split the array into two halves of about n/2 elements each. Enumerate all subsets of each half (2^(n/2) each), recording each subset's (size, sum) pair, and group each half's sums by subset size. Then, for every way of splitting the required total subset size between the two halves, look through the size-grouped sums of each half (sorting them and using a two-pointer or binary-search scan) to find the combination whose combined sum is closest to half of the total array sum. This reduces the exponent from n to roughly n/2, exploiting n <= 20 to make the search tractable. Time: O(2^(n/2) * n) Space: O(2^(n/2))

Iterate over every one of the 2^n possible subsets using a bitmask, and for each one, count how many elements it selects and compute the sum of those elements. Only consider subsets whose size matches the required split (floor(n/2) or ceil(n/2)), and among those track the minimum absolute difference between twice the subset sum and the total array sum (which equals the difference between the two subsets' sums). This checks every possible split directly. Time: O(2^n * n) Space: O(1) extra

1. Fix the target size of one subset as floor(n/2). 2. Try including or excluding each element for THAT subset in turn, tracking how many elements and what sum have been committed to it so far. 3. Prune eagerly: stop growing a branch once the subset already has floor(n/2) elements, or once too few elements remain to ever reach that target count.

Time: O(2^n) in the worst case, though the eager size-based pruning meaningfully reduces the practical search space, manageable given n<=20. Space: O(n) for the recursion depth and tracking the currently-committed subset.

Test n = 1 (one subset gets the element, the other is empty), negative values included, and n = 20 for performance.

Be ready to mention that this is closely related to the classic 'Partition Problem' (split into two subsets with EQUAL sum, no size constraint) - Tug of War adds the extra constraint that subset SIZES must also be nearly equal, which is exactly what necessitates tracking element COUNT alongside sum during the search.