半数集问题 (Java代码）

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			int n=sc.nextInt();
			long []a=new long[1000];
			a[1]=1;
			int sumA=0;
			for (int i =1; i <=n/2; i++) {
				int sum=0;
				for (int j =1; j <=i/2; j++) {
					sum+=a[j];
				}
				a[i]=sum+1;
				sumA+=a[i];
			}
			a[n]=sumA+1;
		System.out.println(a[n]);
      }
	}

}