当前位置:首页 » Project Euler » 详细页

Special subset sums: testing 题号:105 难度: 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).

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 (right click and "Save Link/Target As..."), a 4K 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, A1, A2, ..., Ak, and find the value of S(A1) + S(A2) + ... + S(Ak).

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

Solution

根据第103题的判定方法,先把集合排序为从小到大的数组,之后依次判断数字范围(对前$n$个数字,前$n/2+1$个数字组成的子集A与后$n/2$个数字组成的子集B应满足条件2),再判断其所有子集是否存在和相等的情况($S(A)$与$S(B)$是否相等)。

Code

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

public final class p105 {
    
    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(){
		String fileName="p105_sets.txt";
		int ans=0;
		try(FileReader fr=new FileReader(fileName);
				BufferedReader in = new BufferedReader(fr);){
			String line;
			while((line=in.readLine())!=null){
				String tmp[]=line.split(",");
				ArrayList<Integer> a=new ArrayList<Integer>();
				for(String s:tmp)
					a.add(Integer.parseInt(s));
				if(solve(a)){
					for(int b:a) ans+=b;
				}
			}
		}catch(IOException e){
			e.printStackTrace();
			return null;
		}
        return Integer.toString(ans);
    }

    static private boolean check(Integer[] b){
        HashSet<Integer> sum=new HashSet<Integer>();
        for(int s=1;s<(1<<b.length);s++){
        	int res=0;
        	int ss=s;
        	for(int i=0;i<b.length&&ss>0;i++,ss>>=1) if((ss&1)!=0)
        		res+=b[i];
        	if(sum.contains(res)) return false;
        	sum.add(res);
        }
        return true;
    }
    
    static public boolean solve(ArrayList<Integer> a){
    	Integer b[]=new Integer[a.size()];
  		a.toArray(b);
  		Arrays.sort(b);
  		for(int i=1;i<b.length;i++){
  			if(b[i]<=b[i-1]) return false;
  			int sum1=0;
  			for(int j=0;j<i/2+1;j++) sum1+=b[j];
  			int sum2=0;
  			for(int j=0;j<i/2;j++) sum2+=b[i-j];
  			if(sum1<=sum2) return false;
  		}
  		return check(b);
    }
}
73702
26ms