Building integers

Muche easier solution, I think:

For each new number $n$ of the list, add $n$ to each possible sums so far.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

numbers = [733, ..., 187]
sums = 1000 * [0]
sums[0] = 1

for n in numbers:
    for i in xrange(999-n, -1, -1):
        if sums[i] and i+n < 1000:
            sums[i+n] = 1

print sum(sums) - 1

We have to go from 999 to 0 instead of 0 to 999, because we don't want to add $n$ to a result we just got by adding $n$ previously.

I thought I might need to memoise for a quick result. Nope. Just using a SortedList was either enough or more than enough.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

## https://brilliant.org/problems/building-integers/

from sortedcontainers import SortedList

available=SortedList([733, 854, 10, 397, 408, 238, 298, 741, 884, 499, 709, 938, 435, 930, 120, 125, 590, 300, 438, 209, 456, 686, 442, 296, 228, 655, 512, 652, 281, 926, 176, 222, 760, 961, 836, 606, 842, 802, 5, 359, 592, 327, 571, 161, 562, 533, 470, 446, 642, 583, 716, 886, 550, 192, 61, 65, 719, 452, 545, 792, 354, 77, 806, 870, 812, 491, 477, 346, 693, 406, 831, 201, 398, 790, 185, 713, 568, 182, 814, 822, 196, 604, 51, 682, 235, 166, 681, 151, 572, 778, 375, 513, 736, 413, 762, 259, 869, 537, 31, 936, 162, 839, 363, 811, 628, 764, 826, 744, 994, 19, 768, 380, 115, 154, 853, 728, 444, 178, 203, 956, 284, 779, 710, 119, 786, 626, 603, 745, 459, 66, 60, 160, 474, 914, 90, 640, 857, 85, 925, 797, 528, 981, 972, 402, 793, 819, 581, 429, 451, 885, 84, 931, 123, 647, 833, 593, 522, 163, 78, 772, 935, 957, 2, 960, 422, 314, 840, 684, 827, 71, 804, 503, 759, 975, 206, 619, 255, 117, 538, 180, 729, 582, 367, 72, 369, 667, 921, 113, 138, 698, 646, 286, 838, 348, 414, 577, 15, 757, 521, 187])

def partition(k,remaining=available,chain=[]):
    pos=remaining.bisect_left(k)
    if pos<len(remaining) and remaining[pos]==k:
        return True
    else:
        while True:
            if pos==0:
                return False
            else:
                nextK=k-remaining[pos-1]
                if nextK<0:
                    print ('------>really?')
                    return False
                else: 
                    nextRemaining=remaining.copy()
                    nextRemaining.discard(remaining[pos-1])
                    result=partition(nextK,nextRemaining)
                    if result: return result
            pos-=1

count=0
for i in range(1,1000):
    count+=partition(i)
print (count)

EDIT: Actually, upon reflection, it seems that the correct answer is $\boxed{976}$ , not $\boxed{977}$ . In my original python solution, I was including the empty subset in the powerset calculation, which adds 0 to the set of sums, and 0 is not a positive integer.

I solved this with a pretty quick and simple ad-hoc approach. In python:

from itertools import combinations
from itertools import chain

# From https://docs.python.org/2/library/itertools.html
def powerset(iterable):
  "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
  s = list(iterable)
  return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

s = set([733, 854, 10, 397, 408, 238, 298, 741, 884, 499, 709, 938, 435, 930, 120, 125, 590, 300, 438, 209, 456, 686, 442, 296, 228, 655, 512, 652, 281, 926, 176, 222, 760, 961, 836, 606, 842, 802, 5, 359, 592, 327, 571, 161, 562, 533, 470, 446, 642, 583, 716, 886, 550, 192, 61, 65, 719, 452, 545, 792, 354, 77, 806, 870, 812, 491, 477, 346, 693, 406, 831, 201, 398, 790, 185, 713, 568, 182, 814, 822, 196, 604, 51, 682, 235, 166, 681, 151, 572, 778, 375, 513, 736, 413, 762, 259, 869, 537, 31, 936, 162, 839, 363, 811, 628, 764, 826, 744, 994, 19, 768, 380, 115, 154, 853, 728, 444, 178, 203, 956, 284, 779, 710, 119, 786, 626, 603, 745, 459, 66, 60, 160, 474, 914, 90, 640, 857, 85, 925, 797, 528, 981, 972, 402, 793, 819, 581, 429, 451, 885, 84, 931, 123, 647, 833, 593, 522, 163, 78, 772, 935, 957, 2, 960, 422, 314, 840, 684, 827, 71, 804, 503, 759, 975, 206, 619, 255, 117, 538, 180, 729, 582, 367, 72, 369, 667, 921, 113, 138, 698, 646, 286, 838, 348, 414, 577, 15, 757, 521, 187])
s2 = set(s) # Sums we know exist

# Add sums for all subsets of size 2 or 3, which are quite tractable
for c in combinations(s, 2):
  if sum(c) < 1000:
    s2.add(sum(c))

for c in combinations(s, 3):
  if sum(c) < 1000:
    s2.add(sum(c))

# Obviously, we can't brute force check all subsets - That would be 2^200 iterations.
# Fortunately, after checking subsets of sizes 2 and 3, the remaining [missed] values are few:
sorted(set(range(1,1000)) - s2)
# Prints: [1, 3, 4, 6, 8, 9, 11, 13, 14, 15, 18, 23, 28, 32, 35, 37, 40, 42, 45, 47, 49, 54, 57, 59, 64, 69]

# Thus, we can simply brute force check all subsets containing values < 70, and get complete coverage.
# There are only 11:
s3 = set([x for x in s if x < 70])
sorted(s3) # [2, 5, 10, 15, 19, 31, 51, 60, 61, 65, 66]

for c in powerset(s3):
  if len(c) and sum(c) < 1000:
    s2.add(sum(c))

# Finally, the answer:
len(s2) # 976