ACM (TJU) : 2821


// http://acm.tju.edu.cn/toj/showp2821.html

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int main ()
{
    int n;

    while ( cin >> n && n ) {

        int a [20];

        for ( int i = 0; i < n; i++ )
            cin >> a [i];

        int binary [20] = {0};
        int minimum = 99999;

        for ( int i = 0; i < ceil (n / 2); i++ ) {
            binary [i] = 1;

            sort (binary, binary + n);

            do {
                int team1 = 0;
                int team2 = 0;

                for ( int j = 0; j < n; j++ ) {
                    if ( binary [j] )
                        team1 += a [j];
                    else
                        team2 += a [j];
                }

                int difference;

                if ( team1 > team2 )
                    difference = team1 - team2;
                else
                    difference = team2 - team1;

                if ( minimum > difference )
                    minimum = difference;

            } while ( next_permutation (binary, binary + n) );
        }

        cout << minimum << endl;
    }

    return 0;
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s