1.4 Two Subsets with Min Difference

Assumption: Given array.length >= 2 of size n

Input: int[] array [1,3,2]

Output: int minDifference

Solution:

1. n levels in the tree, each level consider one number in the array

2. 2 state: add the number or not

3. Stop condition: subset size is half of the array and all numbers are considered.

Need: curSum, totalSum, index, subset size(count)

public int minDifference(int[] array) {
  int[] min = new int[1];
  min[0] = Integer.MAX_VALUE;
  int totalSum = 0;
  for (int num : array) {
    total += num;
  }
  helper(array, min, 0, 0, 0, totalSum);
}

private void helper(int[] array, int[] min, int index, int curSum, int count, int totalSum) {
  //base case
  if (index == array.length) {
    if (count == array.length / 2) {
      min[0] = Math.min(Math.abs(curSum - (totalSum - curSum)), min[0]);
    }
    return;
  }
  //case 1: add the number
  curSum += array[index];
  helper(array, min, index + 1, curSum, ++count, totalSum);
  //case 2: not adding the number
  curSum -= array[index]; //remove before returning to previous level
  helper(array, min, index + 1, curSum, --count, totalSum);
}