TopCoder problem, failed.

jewelry.py

'''
for instructions, check
https://www.evernote.com/shard/s46/sh/5353dced-48b4-4158-9a8f-46607d810845/2dc3d625ef7263de7ccfeda0ab7dd0e2
and archived note in google keep.
btw: I failed this problem T^T
'''

def nCr(n, r):
    from itertools import izip
    return reduce(lambda x, y: x * y[0] / y[1], izip(xrange(n - r + 1, n+1), xrange(1, r+1)), 1)
    
from pprint import pprint
from collections import defaultdict

# case 1: passed
#values = [1000,1000,1000,1000,1000,
# 1000,1000,1000,1000,1000,
# 1000,1000,1000,1000,1000,
# 1000,1000,1000,1000,1000,
# 1000,1000,1000,1000,1000,
# 1000,1000,1000,1000,1000]

# case 2: passed
# values = [3,3,2,2,1,1]

# case 3: passed
#values = [2,2,3,3]

# case 4: failed
values = [7,7,8,9,10,11,1,2,2,3,4,5,6]

values.sort(reverse=True)
length = len(values)
groups = [0]
for i in range(1, length):
    if values[i] == values[i-1]: continue
    else: groups.append(i)
print groups 

fromBegin = [defaultdict(lambda:0) for i in range(length)]
fromBegin[0][values[0]] = 1
fromBegin[0][0] = 1
for i in range(1, length-1):
    fromBegin[i][values[i]] = 1
    fromBegin[i][0] = 1
    for j in range(i):
        for k, v in fromBegin[j].iteritems():
            fromBegin[i][k+values[i]] += v
fromBegin[-1][0] = 1
# pprint(fromBegin)

tillEnd = [defaultdict(lambda:0) for i in range(length)]
tillEnd[length-2][values[length-1]] = 1
for i in reversed(range(length-2)):
    tillEnd[i] = tillEnd[i+1].copy()
    tillEnd[i][values[i+1]] += 1
    for k,v in tillEnd[i+1].iteritems():
        tillEnd[i][k+values[i+1]] += v
pprint(tillEnd)

# get the answer
answer = 0
for i in range(len(groups)):
    current, next = groups[i], groups[i+1] if i!=len(groups)-1 else length
    for k, v in fromBegin[current-1].iteritems():
        for j in range(next-current):
            common = k+(j+1)*values[current]
            if common in tillEnd[current+j]: 
                # print x
                x = nCr(next-current, j+1)*tillEnd[current+j][common]
                answer += x
    
print answer