import java.util.LinkedList;
import java.util.List;

//This solution is generic with the only limitation that the amount of days is 32 or less.
//The total number of days the IRS has pegged Steve at can be any number from 1 up to however mana days of data there is.
//Remove the remark // characters off the 2 removed lines to get a decent estimate on the speed of this algorithm.
//
//NB: This requires java 1.5.
//NB2: I've dressed it up a bit to print nicely and the like, but the actual meat is just the go() method.
// --Reinier Zwitserloot
public class Steve3 {
	private static final int[] N = new int[] {
		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
	};
	private static final int L = N.length;
	private static final int X = 9;
	
	private static class Solution {
		public int sum;
		public int ct;
		public int used = 0;
		
		Solution() {}
		
		Solution(Solution parent, int n, int idx) {
			sum = parent.sum + n;
			ct = parent.ct + 1;
			used = parent.used | (1 << idx);
		}
		
		boolean beats(Solution other) {
			int dist = sum < 0 ? -sum : sum;
			int dist2 = other.sum < 0 ? -other.sum : other.sum;
			return dist < dist2;
		}
		
		public @Override String toString() {
			char[] p = new char[L];
			StringBuilder descriptive = new StringBuilder();
			
			descriptive.append('[');
			for ( int i = 0 ; i < L ; i++ ) {
				boolean marked = ((used >>> i) & 1) == 1;
				p[i] = marked ? '1' : '0';
				if ( marked ) descriptive.append(N[i] + ", ");
			}
			descriptive.setLength(descriptive.length() -2);
			descriptive.append(']');
			return String.format("A sum of %d can be reached using use pattern %s:\n%s", sum, new String(p), descriptive);
		}
	}
	
	public static void main(String[] args) {
		long start = System.currentTimeMillis();
//		for ( int i = 0 ; i < 9999 ; i++ ) go();
		Solution answer = go();
		long end = System.currentTimeMillis();
		double timeTaken = end - start;
//		timeTaken /= 10000;
		System.out.printf("Solution found in %f millis\n%s\n", timeTaken, answer);
	}
	
	public static Solution go() {
		List<Solution> s = new LinkedList<Solution>();
		List<Solution> s2 = new LinkedList<Solution>();
		Solution best = new Solution();
		best.sum = Integer.MAX_VALUE;
		s.add(new Solution());
		for ( int i = 0 ; i < L ; i++ ) {
			s.addAll(s2);
			s2.clear();
			for ( Solution a : s ) {
				Solution b = new Solution(a, N[i], i);
				if ( b.ct == X ) {
					if ( b.sum == 0 ) return b;
					if ( b.beats(best) ) best = b;
				} else s2.add(b);
			}
		}
		return best;
	}
}