import java.util.Arrays;

class SplitCoin {
    public int split(int[] coins) {
        int[] upper = null;
        int[] lower = null;
        int smallestDifference = 0;
        
        Arrays.sort(coins);

        lower = Arrays.copyOfRange(coins, 0,coins.length-1);
        upper = Arrays.copyOfRange(coins, coins.length-1,coins.length); //(after sorting) put the largest element in upper            

        smallestDifference = Math.abs(arraySum(upper) - arraySum(lower));
        return findSmallestDifference(lower, upper, arraySum(lower), arraySum(upper), smallestDifference);
    }
    
    private int findSmallestDifference (int[] lower, int[] upper, int lowerSum, int upperSum, int smallestDifference) {
        int[] newUpper = null, newLower = null;
        int currentDifference = Math.abs(upperSum-lowerSum);
        if (currentDifference < smallestDifference) {
            smallestDifference = currentDifference;
        } 
        if (lowerSum < upperSum || lower.length < upper.length || lower[0] > currentDifference 
                || lower[lower.length-1] > currentDifference 
                || lower[lower.length-1] < upper[0]/lower.length) {
            return smallestDifference;
        }
        for (int i = lower.length-1; i >= 0 && smallestDifference > 0; i--) {           
           newUpper = addElement(upper, lower[i]);
           newLower = removeElementAt(lower, i);
           smallestDifference = findSmallestDifference(newLower, newUpper, 
                   lowerSum - lower[i], upperSum + lower [i], smallestDifference);
        }
        return smallestDifference;
    }
    
    private int arraySum (int[] array) {
        int result = 0;        
        for (int current : array){
            result += current;
        }
        return result;
    }
    
    private int[] addElement (int[] array, int element) {
        int[] result = new int[array.length+1];
        System.arraycopy(array, 0, result, 0, array.length);
        result[array.length] = element;
        return result;
    }
    
    private int[] removeElementAt (int[] array, int index) {
        int[] result = new int[array.length-1];
        System.arraycopy(array, 0, result, 0, index);
        System.arraycopy(array, index+1, result, index, result.length-index);
        return result;
    }
    
    public static void main(String[] args) { //debug
        int[] temp = {851,886,91,128,942,395,976,872,337,334};
/*      
        int[] temp = {100000,919,445,108,329,566,51,611,69,289,
                479,671,916,185,667,450,988,107,861,668,186,277,
                123,551,352,350,997,189,654,151};
*/
/*
        int[] temp = {100000,60000,60000,60000,60000,60000,60000,60000,60000,
            60000,60000,60000,60000,60000,60000,60000,60000,60000,
            60000,60000,60000,60000,60000,60000,60000,60000,60000,
            60000,60000,60000};
*/
        SplitCoin sc = new SplitCoin();
        
        System.out.println(sc.split(temp));
    }
    
}