Problem 105 of Project Euler is closely related to Problem 103 as has been mentioned in both problem descriptions. The problem formulation for this problem is

Let S(A) represent the sum of elements in set A of sizen. We shall call it a special sum set if for any two non-empty disjoint subsets, B and C, the following properties are true:

S(B) ≠ S(C); that is, sums of subsets cannot be equal.If B contains more elements than C then S(B) > S(C).

For example, {81, 88, 75, 42, 87, 84, 86, 65} is not a special sum set because 65 + 87 + 88 = 75 + 81 + 84, whereas {157, 150, 164, 119, 79, 159, 161, 139, 158} satisfies both rules for all possible subset pair combinations and S(A) = 1286.

Using sets.txt, a text file with one-hundred sets containing seven to twelve elements (the two examples given above are the first two sets in the file), identify all the special sum sets, A_{1}, A_{2}, …, A_{k}, and find the value of S(A_{1}) + S(A_{2}) + … + S(A_{k}).

To be completly honest, I haven’t gotten all that many new insights from solving this problem compared to Problem 103. What we need here is to check if a set of numbers fulfils both properties. In problem 103 we generated specific functions for checking each of the properties, so I have just reused these functions in order to solve this problem. I did discover a bug in Problem 103 when I solved this, but that has been corrected now, so I did get something from the problem but not much.

The all we need is a bit of wrapping the problem in something that can read the input file and sum up all the sets that fulfils the properties. Personally I think that solving this problem first will make a lot more sense, since it forces you to write functions for checking if a set is valid.

The code for this problem looks as in C#

int result = 0; int j = 0; string[] lines = File.ReadAllLines(filename); foreach (string line in lines) { //Parse the line string[] segments = line.Split(','); int dim = segments.Length; int[] numbers = new int[dim]; for(int i = 0; i < dim; i++){ numbers[i] = Convert.ToInt32(segments[i]); } Array.Sort(numbers); if (VerifyRule2(numbers)) { int[] s = MakeSubsetSums(numbers); if (VerifyRule1(s)) { result += numbers.Sum(); j++; } } }

this runs in

The sum of valid sss is 73702 Solution took 33,358 ms

You can see the methods either in Problem 103, or in the source code.

## Wrapping up

Having already solved problem 103, this problem was close to trivial. However, I think the problem on it’s own is a rather fun one which does require a whole lot of thinking.

You are as always welcome to take a look at the source code, and as always I would love to hear from you about how you solved the problem.

Written by Kristian on 14 July 2012

Topics: Project Euler