import math
from itertools import combinations

T = int(raw_input().strip())

for t in xrange(T):

    N = int(raw_input().strip())
    
    ### Find divisors
    divisors = []
    divisors.append(1)

    sqrtN = int(math.sqrt(N))
    for i in xrange(2, sqrtN):
        if N % i == 0:
            divisors.append(i)
            if i * i != N:
                divisors.append(N/i)
    
    ### Get sum of divisors
    sumDiv = sum(divisors)

    weird = False
    if sumDiv > N:
        weird = True
        i = 1
        
        ### For each subset, calculate the sum
        while i < len(divisors):
            for c in combinations(divisors, i):
                if sum(c) == N:
                    weird = False
                    i = len(divisors)
                    break
            i += 1

    if weird:
        print 'weird'
    else:
        print 'not weird'

Divisor 을 구하는거까지는 괜찮은거같은데요.
그후에 subset 의 sum 을구하는대서 오래걸려요.
위에 코드는 콤비네이션 라이브러리를 쓴거구요.
다이나믹프로그래밍으로도 접근해봤는데 비슷하게 오래걸리네요.
어떻게 접근하는게 좋을까요?