Find smallest set of i*2 or i+1 subitems which sum makes N

subset_sum.py

# you can use print for debugging purposes, e.g.
# print "this is a debug message"


def solution(N):
    q = [(1,)]
    visited = set()
    for seq in q:
        s = sum(seq)
        if s == N:
            return len(seq) + 1
        elif s > N:
            continue
        key = (seq[-1], s)
        if key in visited:
            continue
        visited.add(key)
        q.append(seq + (seq[-1] * 2,))
        q.append(seq + (seq[-1] + 1,))
    return -1

print solution(18)
# should print 6
print solution(220)
# should print 12
print solution(221)
# no such solution? print -1 or None
print solution(2001)
# answer is 16 (set (1, 2, 4, 8, 16, 17, 18, 36, 37, 74, 148, 149, 298, 596, 597))
print solution(3001)
# answer is 16 as well
# look at this set: (1, 2, 4, 8, 16, 17, 34, 68, 69, 138, 139, 278, 556, 557, 1114)