DSA 450 Notes

Problem Statement

Given a set of n integers, divide it into two subsets of equal size (or sizes differing by 1 if n is odd) such that the difference of sums of the two subsets is minimized.

Example:

Input: arr = [3, 4, 5, -3, 100, 1, 89, 54, 23, 20]
Output: 
Set 1: [4, 100, 1, 23, 20] Sum = 148
Set 2: [3, 5, -3, 89, 54] Sum = 148
Difference = 0

Input: arr = [23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4]
Output: Minimum difference with equal sized subsets

Approach 1: Brute Force (Generate All Partitions)

Intuition

Generate all possible ways to select n/2 elements for one subset. The remaining elements form the other subset. Track the partition with minimum difference.

Algorithm

Calculate total sum
Use backtracking to select n/2 elements
Track the sum of selected elements
Other subset sum = total - selected sum
Update minimum difference

java

import java.util.*;

class Solution {
    private int minDiff;
    private List<Integer> bestSet1, bestSet2;
    
    public void solve(int[] arr, int index, int count, int sumSelected,
                      int totalSum, int targetCount, List<Integer> currentSet,
                      boolean[] selected) {
        // Found a valid partition
        if (count == targetCount) {
            int diff = Math.abs(2 * sumSelected - totalSum);
            if (diff < minDiff) {
                minDiff = diff;
                bestSet1 = new ArrayList<>(currentSet);
                bestSet2 = new ArrayList<>();
                for (int i = 0; i < arr.length; i++) {
                    if (!selected[i]) {
                        bestSet2.add(arr[i]);
                    }
                }
            }
            return;
        }
        
        // Not enough elements left
        if (index >= arr.length) return;
        if (arr.length - index < targetCount - count) return;
        
        // Include current element
        currentSet.add(arr[index]);
        selected[index] = true;
        solve(arr, index + 1, count + 1, sumSelected + arr[index],
              totalSum, targetCount, currentSet, selected);
        currentSet.remove(currentSet.size() - 1);
        selected[index] = false;
        
        // Exclude current element
        solve(arr, index + 1, count, sumSelected, totalSum, targetCount,
              currentSet, selected);
    }
    
    public void tugOfWar(int[] arr) {
        int n = arr.length;
        int totalSum = 0;
        for (int x : arr) totalSum += x;
        
        minDiff = Integer.MAX_VALUE;
        boolean[] selected = new boolean[n];
        
        solve(arr, 0, 0, 0, totalSum, n / 2, new ArrayList<>(), selected);
        
        // Print result
        System.out.print("Set 1: ");
        int sum1 = 0;
        for (int x : bestSet1) {
            System.out.print(x + " ");
            sum1 += x;
        }
        System.out.println(" Sum = " + sum1);
        
        System.out.print("Set 2: ");
        int sum2 = 0;
        for (int x : bestSet2) {
            System.out.print(x + " ");
            sum2 += x;
        }
        System.out.println(" Sum = " + sum2);
        
        System.out.println("Minimum Difference = " + minDiff);
    }
}

Complexity Analysis

Time Complexity: O(2^n) - Generate all subsets of size n/2
Space Complexity: O(n) - Recursion stack and current set

Approach 2: Optimal (With Pruning)

Intuition

Add pruning conditions to skip branches that cannot lead to a better solution.

Algorithm

Sort array for better pruning
If current difference already exceeds best, prune
Skip unnecessary explorations

java

import java.util.*;

class Solution {
    private int minDiff;
    private List<Integer> bestSet1, bestSet2;
    
    private void solve(int[] arr, int index, List<Integer> set1, List<Integer> set2,
                       int sum1, int sum2, int n, int size1, int size2) {
        if (set1.size() == size1 && set2.size() == size2) {
            int diff = Math.abs(sum1 - sum2);
            if (diff < minDiff) {
                minDiff = diff;
                bestSet1 = new ArrayList<>(set1);
                bestSet2 = new ArrayList<>(set2);
            }
            return;
        }
        
        if (index >= n) return;
        
        int remaining = n - index;
        int need1 = size1 - set1.size();
        int need2 = size2 - set2.size();
        
        // Can add to set1
        if (need1 > 0 && remaining >= need1) {
            set1.add(arr[index]);
            solve(arr, index + 1, set1, set2, sum1 + arr[index], sum2, n, size1, size2);
            set1.remove(set1.size() - 1);
        }
        
        // Can add to set2
        if (need2 > 0 && remaining >= need2) {
            set2.add(arr[index]);
            solve(arr, index + 1, set1, set2, sum1, sum2 + arr[index], n, size1, size2);
            set2.remove(set2.size() - 1);
        }
    }
    
    public int tugOfWar(int[] arr) {
        int n = arr.length;
        int size1 = n / 2;
        int size2 = n - size1;
        minDiff = Integer.MAX_VALUE;
        
        solve(arr, 0, new ArrayList<>(), new ArrayList<>(), 0, 0, n, size1, size2);
        
        System.out.println("Minimum Difference = " + minDiff);
        return minDiff;
    }
}

Complexity Analysis

Time Complexity: O(2^n) - Still exponential but with pruning
Space Complexity: O(n) - Recursion stack

Key Takeaways

Equal Size Constraint: Must select exactly n/2 elements for one subset
Difference Minimization: Goal is min |sum1 - sum2|
Pruning: Check remaining elements vs required elements
Negative Numbers: Algorithm handles negative numbers correctly
Applications: Fair team division, resource allocation
NP-Hard: Finding optimal partition is computationally hard

Tug of War

Problem Statement

Approach 1: Brute Force (Generate All Partitions)

Intuition

Algorithm

Complexity Analysis

Approach 2: Optimal (With Pruning)

Intuition

Algorithm

Complexity Analysis

Key Takeaways