package net.wuenschenswert;

import java.util.List;
import java.util.ArrayList;

public class ZeroSum {
  final int[] monthsTakings;
  final int n;

  int bestSum = Integer.MAX_VALUE;
  int[] bestSelection;

  public ZeroSum(int[] monthsTakings, int n) {
    this.monthsTakings = monthsTakings;
    this.n = n;
  }

  public void compute() {
    bestSelection = new int[n];
    select(new int[n], 0,0,0);
  }

  private void select(int[] selection, int i, int sum, int nSelected) {
    if(nSelected == n) {
      if(Math.abs(sum) < Math.abs(bestSum)) {
        bestSum = sum;
        System.arraycopy(selection, 0, bestSelection, 0, n);
      }
      return;
    }
    // may skip up to the point where we have to take the rest
    for( ; i <= monthsTakings.length-(n-nSelected); ++i) {
      // try adding
      int elt = monthsTakings[i];
      selection[nSelected] = elt;
      select(selection, i+1, sum+elt, nSelected+1);
      // exit if we already have the best solution
      if(bestSum == 0)
        return;
    };
  }

  static int exampleData[] = {-50,-21,13,171,14,-42,-58,109,4,7,-23,-44,-98,-121,101, 33,87,-121,-40,-65,43,54,-45,-12,-12,38,25,3,7,8,};

  public static void main(String[] args) {
    ZeroSum zeroSum=null;
    long start = System.currentTimeMillis();
    for(int i=0; i<10000; ++i) {
      zeroSum = new ZeroSum(exampleData, 9);
      zeroSum.compute();
    }
    long end = System.currentTimeMillis();
    // output:
    List<Integer> ints = new ArrayList<Integer>();
    for (int i = 0; i < zeroSum.bestSelection.length; i++) {
      ints.add(zeroSum.bestSelection[i]);
    }
    System.out.println("After "+(end-start)+"ms: Best with "+zeroSum.bestSum+": "+ints);
  }

}