Apparently, this is a very complicated problem,
but 1115 allows solutions with naive implementations.
I almost used brute force here, with some little optimizations (like looking for solutions for the next few sums while working on the 'current' one).