Google CodeJam EuroPython 2012, Problem A "Quake Live" solution

quake_live.py

#!/usr/bin/env python
# coding: utf-8

import itertools

def find_min_skill_difference(skills):
    n = len(skills)
    if n == 2:
        return abs(skills[0] - skills[1])
    skills.sort()
    players_skills = dict(enumerate(skills))

    choices = list(itertools.combinations(players_skills.keys(), n / 2))
    l = len(choices)
    options = []
    for i in xrange(l):
        for j in xrange(l):
            a = choices[i]
            b = choices[j]
            if len(set(a) - set(b)) == n/2:
                options.append(abs(sum(players_skills[x] for x in a) - sum(players_skills[x] for x in b)))

    options.sort()

    return options[0]


def main():
    n = int(raw_input())
    for i in range(n):
        skills = [int(k) for k in raw_input().split()[1:]]
        print "Case #%s: %s" % (i+1, find_min_skill_difference(skills))

if __name__ == "__main__":
    main()