Challenge on http://www.opengarden.com/jobs.html

cities.py

import sys
a=[18897109,12828837, 9461105, 6371773, 5965343, 5946800, 5582170, 5564635, 5268860, 4552402, 4335391, 4296250, 4224851, 4192887, 3439809, 3279833, 3095313, 2812896, 2783243, 2710489, 2543482, 2356285, 2226009, 2149127, 2142508, 2134411]
CUT=100000000
#a=[1,2,3,4]
#CUT=5

# the recursion
def r(pos, level):
    global a
    if level == 1:
        yield [a[pos]]
    else:
        for i in range(pos+1,len(a)):
            for e in r(i, level-1):
                yield [a[pos]]+e

# trying a short path, based on the decreasing average of cities' size
av=len(a)*CUT/sum(a)
#print av # num of elements based on the sum average
s=0
for i in range(1,len(a)):
    s=s+a[i-1]-a[i]
difaverage=s/(len(a)-1) # the difference average between pairs
m=av-int(av*av*(difaverage/float(sum(a))))
mm=av+int(av*av*(difaverage/float(sum(a))))
#print m,mm # num of elements (minus,plus) the percentual difaverage

for i in range(len(a)):
    for j in range(m,mm):
        for k in r(i, j):
            s=sum(k)
            if s == CUT:
                print k, sum(k), j
                sys.exit() #stop doing after found
            #else:
            #    sys.stdout.write("\r"+str(s)) # just to follow the process