Length Sum Recipes

lengths = ( (20,) * 2 +
            (25,) * 2 +
            (30,) * 2 +
            (35,) * 2 +
            (40,) * 2 +
           (100,) * 4 +
           (200,) * 2 +
           (515,) * 4)

counts = {}
for l in lengths:
  counts[l] = counts.get(l, 0) + 1
counts = tuple(sorted(counts.items(), reverse=True))

explore = [(0, {}, 0)]
found = {}

while explore[0][0] < len(counts):
  sel, recipe, sum = explore.pop(0)
  if (sum, sel) not in found:
    for i in range(sel, len(counts)):
      l, c = counts[i]
      explore.append((sel + 1, recipe, sum))
      for j in range(1, c + 1):
        explore.append((sel + 1, {**recipe, **{l: j}}, sum + l * j))
    found[(sum, sel)] = recipe

lastsum = 0
for sum, sel in sorted(found):
  if sum != lastsum:
    print(f'{sum}: {found[(sum, sel)]}')
    lastsum = sum