Project Euler > Problem 106 > Special subset sums: meta-testing (Java Solution)

Problem:

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

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

For this problem we shall assume that a given set contains n strictly increasing elements and it already satisfies the second rule.

Surprisingly, out of the 25 possible subset pairs that can be obtained from a set for which n = 4, only 1 of these pairs need to be tested for equality (first rule). Similarly, when n = 7, only 70 out of the 966 subset pairs need to be tested.

For n = 12, how many of the 261625 subset pairs that can be obtained need to be tested for equality?

NOTE: This problem is related to problems 103 and 105.

Solution:

25164150

Code:
The solution may include methods that will be found here: Library.java .

public interface EulerSolution{

public String run();

}

/* 
 * Solution to Project Euler problem 6
 * By Nayuki Minase
 * 
 * http://nayuki.eigenstate.org/page/project-euler-solutions
 * https://github.com/nayuki/Project-Euler-solutions
 */


public final class p006 implements EulerSolution {
	
	public static void main(String[] args) {
		System.out.println(new p006().run());
	}
	
	
	private static final int N = 100;
	
	
	public String run() {
		int sum = 0;
		int sum2 = 0;
		for (int i = 1; i <= N; i++) {
			sum += i;
			sum2 += i * i;
		}
		/* 
		 * For the mathematically inclined:
		 *   sum  = N(N + 1) / 2.
		 *   sum2 = N(N + 1)(2N + 1) / 6.
		 */
		return Integer.toString(sum * sum - sum2);
	}
	
}