### Special subset sums: optimum题号：103 难度： 45 中英对照

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).

If S(A) is minimised for a given n, we shall call it an optimum special sum set. The first five optimum special sum sets are given below.

n = 1: {1}
n = 2: {1, 2}
n = 3: {2, 3, 4}
n = 4: {3, 5, 6, 7}
n = 5: {6, 9, 11, 12, 13}

It seems that for a given optimum set, A = {a1, a2, ... , an}, the next optimum set is of the form B = {b, a1+b, a2+b, ... ,an+b}, where b is the "middle" element on the previous row.

By applying this "rule" we would expect the optimum set for n = 6 to be A = {11, 17, 20, 22, 23, 24}, with S(A) = 117. However, this is not the optimum set, as we have merely applied an algorithm to provide a near optimum set. The optimum set for n = 6 is A = {11, 18, 19, 20, 22, 25}, with S(A) = 115 and corresponding set string: 111819202225.

Given that A is an optimum special sum set for n = 7, find its set string.

NOTE: This problem is related to Problem 105 and Problem 106.

### Code

import java.util.HashSet;
public final class p103 {
public static void main(String[] args) {
long start=System.nanoTime();
String result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}
static public String run(){
int a[]=new int[8];
int min=255;
String ans="20313839404245";
for(a[1]=1;a[1]<=36;a[1]++){
for(a[2]=a[1]+1;a[2]<=36;a[2]++){
for(a[3]=a[2]+1;a[3]<a[1]+a[2];a[3]++){
for(a[4]=a[3]+1;a[4]<a[1]+a[2];a[4]++){
for(a[5]=a[4]+1;a[5]<a[1]+a[2]+a[3]-a[4];a[5]++){
for(a[6]=a[5]+1;a[6]<a[1]+a[2]+a[3]-a[5];a[6]++){
for(a[7]=a[6]+1;a[7]<a[1]+a[2]+a[3]+a[4]-a[5]-a[6];a[7]++){
if(check(a)){
int sum=0;
for(int i=1;i<=7;i++) sum+=a[i];
if(sum<min){
min=sum;
ans="";
for(int i=1;i<=7;i++) ans+=a[i];
}
}
}
}
}
}
}
}
}
return ans;
}
static private boolean check(int a[]){
HashSet<Integer> sum=new HashSet<Integer>();
for(int i=1;i<=7;i++) for(int j=i+1;j<=7;j++){
if(sum.contains(a[i]+a[j]))
return false;
}
20313839404245