A test case where your method doesn't work is
que = [1, 1, 50, 50, 50, 1000]
The problem is that you're analyzing things in pairs, and in this example, you want all the 50's to be in the same group. This should be solved though if you remove the pair analysis aspect and just do one entry at a time.
Here's the code that does this
def make_teams(que):
que.sort()
que.reverse()
if len(que)%2: que.insert(0,0)
t1,t2 = [],[]
while que:
if abs(len(t1)-len(t2))>=len(que):
[t1, t2][len(t1)>len(t2)].append(que.pop(0))
else:
[t1, t2][sum(t1)>sum(t2)].append(que.pop(0))
print min(sum(t1),sum(t2)), max(sum(t1),sum(t2)), "\n"
if __name__=="__main__":
que = [2,3,10,5,8,9,7,3,5,2]
make_teams(que)
que = [1, 1, 50, 50, 50, 1000]
make_teams(que)
This give 27, 27 and 150, 1002 which are the answers that make sense to me.
Edit: In review, I find this to not actually work, though in the end, I'm not quite sure why. I'll post my test code here though, as it might be useful. The test just generates random sequence that have equal sums, puts these together and compares (with sad results).
Edit #2: Based in the example pointed out by Unknown, [87,100,28,67,68,41,67,1], it's clear why my method doesn't work. Specifically, to solve this example, the two largest numbers need to both be added to the same sequence to get a valid solution.
def make_sequence():
"""return the sums and the sequence that's devided to make this sum"""
while 1:
seq_len = randint(5, 200)
seq_max = [5, 10, 100, 1000, 1000000][randint(0,4)]
seqs = [[], []]
for i in range(seq_len):
for j in (0, 1):
seqs[j].append(randint(1, seq_max))
diff = sum(seqs[0])-sum(seqs[1])
if abs(diff)>=seq_max:
continue
if diff<0:
seqs[0][-1] += -diff
else:
seqs[1][-1] += diff
return sum(seqs[0]), sum(seqs[1]), seqs[0], seqs[1]
if __name__=="__main__":
for i in range(10):
s0, s1, seq0, seq1 = make_sequence()
t0, t1 = make_teams(seq0+seq1)
print s0, s1, t0, t1
if s0 != t0 or s1 != t1:
print "FAILURE", s0, s1, t0, t1
