题意：
给定一个集合A，包含2^N个数，问是否存在N个数可以组合成A。
思路：
假设存在N个数可以组合成A。取出A中最大的两个数Firs，Second；x=First-Second，x一定位N个数中的一个数；集合A中的元素按照是否包含x可以划分为A＋（包含ｘ），A－（不包含ｘ）；且A＋的大小＝A－的大小＝２＾（Ｎ－１）；
A－可以看作是剩下的N－１个元素组合而成的集合，将A－迭代A（A＝A－），继续执行上述操作，集合的大小不断变为原来的１／２，直至最终只剩下一个元素０；
{
如何不重不漏的求得所有不包含ｘ的元素，即如何求得A-？
首先将A中的所有元素单调不减的顺序排列，然后从小到大处理。
序列S：不包含x的元素所形成的序列。初始为空。
A中的第一个元素为０，将０加入S。
假设序列S已有：ａ１，ａ２……ａｋ，且ａ１＋ｘ，ａ２＋ｘ，……ａｋ＋ｘ都已经从A中删除，则ａＫ＋１一定不包含ｘ。
证明：假设ａｋ＋１包含ｘ
１、若ａｋ＋１－ｘ小于等于ａｋ，则ａｉ＋ｘ（１＜＝ｉ＜＝ｋ）未删除，与已知矛盾。
２、若ａｋ＋１－ｘ大于ａｋ，则ａｋ＋１不是大于ａｋ的第一个元素，与假设矛盾。
固假设错误，所以ａｋ＋１不包含ｘ。
将ａｋ＋１加入序列S，并将ａＫ＋１＋ｘ从A中删除。重复执行加入删除的步骤，直至A为空，此时S即为A－。
}
以上为必要条件，即若存在N个元素可以组合成A，则以上条件满足。
若A可以重复的用A-迭代，直至最后只剩下一个0，那么也存在N个元素可以组合成A。
/* 来自题解 给你n件物品和他们的重量和所有组合，求是否存在这n件物品的重量，满足这些组合 */ #include <cstdio> #include <cstring> #include <cmath> #include <cctype> #include <iostream> #include <algorithm> #include <map> #include <set> #include <vector> #include <string> #include <stack> #include <queue> typedef long long LL; using namespace std; int n, ans[25]; multiset<int> s; int main() { //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); scanf("%d", &n); for (int i = 0, x; i < (1 << n); i++) scanf("%d", &x), s.insert(x); int cnt = 0; for (int i = 1; i <= n; i++){ if(s.size() < 2) break; cnt++; int x = *prev(s.end()) - *prev(prev(s.end())); ans[i] = x; for (auto it = s.begin(); it != s.end(); it++){ int y = *it; auto p = s.upper_bound(x + y); p = prev(p); if(p == s.end() || p == it || *p != x + y){ printf("impossible "); return 0; } s.erase(p); } } if(s.size() != 1 || *s.begin() != 0 || cnt < n) printf("impossible "); else for (int i = 1; i <= n; i++) printf("%d ", ans[i]); return 0; } /**/