Project Euler 103 - Special Subset Sums: Optimum

Official link: https://projecteuler.net/problem=103

Thought Process

Like pretty much everyone who solved this problem, I went with a brute force solution.

Using the given "rule" I generated the "near-optimum set" for n = 7, which is {20, 31, 38, 39, 40, 42, 45}, and then I just generate all subsets "near" the "near-optimum set".

The way I define "near" is as follows: Given a set A = {a, b, c, d} the "x-near" sets are all sets {[a - x, a + x], [b - x, b + x], [c - x, c + x], [d - x, d + x]}

In the case of the problem I generated all "3-near" and "5-near" sets. Then I found the optimum set from both of them, saw they were the same and submitted my answer and it turned out to be correct.

To generate these "x-near" sets I used itertools.product which is essentially to nested for loops in a generator. Definitely a useful tool I will keep for future use!

Finally, the real meat of the problem is the function I made to test if set's are special sum set's. I include my code below with some comments but if you read the code it's fairly self explanatory.