ACdreamOJ 1726 hash 二进制表示下的枚举

http://acdream.info/problem?pid=1726
Problem Description

---

Recently, Losanto find an interesting Math game. The rule is simple: Tell you a number H, and you can choose some numbers from a set {a[1],a[2],……,a[n]}.If the sum of the number you choose is H, then you win. Losanto just want to know whether he can win the game.

Input

There are several cases.
In each case, there are two numbers in the first line n (the size of the set) and H. The second line has n numbers {a[1],a[2],……,a[n]}.0<n<=40, 0<=H<10^9, 0<=a[i]<10^9,All the numbers are integers.

Output

If Losanto could win the game, output “Yes” in a line. Else output “No” in a line.

Sample Input

10 87
2 3 4 5 7 9 10 11 12 13
10 38
2 3 4 5 7 9 10 11 12 13

Sample Output

No
Yes

最大的n值为40，需枚举的状态略多；于是折成两半枚举。前后两段合拼时，不是正向地求和，而是逆向查询，节约了时间

/**
 * 2015年7月17日 下午5:41:50
 * PrjName:acd1726
 * @ Semprathlon
**/
import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args) throws IOException {
		StreamTokenizer cin = new StreamTokenizer(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		HashSet<Long> map = new HashSet<Long>();
		while (cin.nextToken() != StreamTokenizer.TT_EOF) {
			int n = (int) cin.nval;
			cin.nextToken();
			int m = (int) cin.nval;
			map.clear();
			int[] num = new int[n];
			for (int i = 0; i < n; i++) {
				cin.nextToken();
				num[i] = (int) cin.nval;
			}
			int t = (n + 1) / 2;
			for (int i = 0; i < (1 << t); i++) {
				long sum = 0;
				for (int j = 0; j < t; j++) {
					if ((i & (1 << j)) > 0)
						sum += num[j];
				}
				if (sum > m)
					continue;
				map.add(sum);
			}
			int tt = n - t;
			boolean flag = map.contains(m);
			for (int i = 0; i < (1 << tt); i++) {
				long sum = 0;
				for (int j = 0; j < tt; j++) {
					if ((i & (1 << j)) > 0)
						sum += num[t + j];
				}
				if (sum > m)
					continue;
				if (map.contains(m - sum)) {
					flag = true;
					break;
				}
			}
			if (flag)
				out.println("Yes");
			else
				out.println("No");
			// out.flush();
		}
		out.flush();
	}
}