### Special subset sums: meta-testing题号：106 难度： 50 中英对照

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 Problem 103 and Problem 105.

### Code

import java.util.*;

public final class p106 {

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" );
}

public static String run(){
int a[] = {1219 ,1183, 1182, 1115, 1035, 1186, 591, 1197, 1167, 887, 1184, 1175};
Arrays.sort(a);
// 所有的子集
ArrayList<ArrayList<Integer>> sets = MakeSubsets(a);
int size = sets.size();
int ans = 0;
for(int i=0;i<size;i++){
ArrayList<Integer> set1 = sets.get(i);
for(int j=i+1;j<size;j++){
ArrayList<Integer> set2 = sets.get(j);
//不相交
if(set1.size() == set2.size()){
if(!isDisjoint(set1,set2) ){
boolean s=false,t=false;
for(int k=0;k<set1.size() && (!s||!t);k++){
if(set1.get(k) > set2.get(k))
s=true;
if(set1.get(k) < set2.get(k))
t=true;
}
if(s&&t)
ans++;

}

}
}
}
return Integer.toString(ans);
}

// 两个子集元素是否相交 true 相交 false 不相交
public static boolean isDisjoint(ArrayList<Integer> set1,ArrayList<Integer> set2){
for(int x:set1)
if(set2.contains(x))
return true;
return false;
}

// 求出所有的子集
public static ArrayList<ArrayList<Integer>> MakeSubsets(int a[]){
ArrayList<ArrayList<Integer>> sets = new ArrayList<ArrayList<Integer>>();
for(int i=1;i< (int) Math.pow(2,a.length);i++){
ArrayList<Integer> set = MakeSubset(a,i);
}
return sets;

}
// 求出子集
// 利用 和  1 进行与运算 并移位
//  001001 相当于根据 1 所在的位置取 第 2 第 5的位置对应的数
// &000001
//----------
//       1 取出该位置对应的数
// 下面右移一位后
//  000100
// 下面同理了
public static ArrayList<Integer> MakeSubset(int[] a,int m){
ArrayList<Integer> set = new ArrayList<Integer>();
for(int i=0;i<a.length && m>0 ;i++,m>>=1){
if((m&1)==1)
}
21384