P13320 [GCJ 2012 #1B] Equal Sums

我有一个正整数集合 $\mathbf{S}$。你能否找到两个非空且不同的子集，使它们的元素和相等？ **注意**：子集是仅包含自 $\mathbf{S}$ 的元素的集合；若两个子集包含的元素完全相同，则认为它们是相同的，否则为不同子集。

输入的第一行为测试用例数 $\mathbf{T}$。接下来有 $\mathbf{T}$ 组测试数据，每组一行。每组数据首先给出一个整数 $\mathbf{N}$，表示集合 $\mathbf{S}$ 中正整数的个数，随后是 $\mathbf{N}$ 个互不相同的正整数，全部在同一行。

对于每个测试用例，首先输出一行 "Case #x:"，其中 $\mathbf{x}$ 为测试用例编号（从 1 开始）。 * 如果存在 $\mathbf{S}$ 的两个不同子集，其元素和相等，则输出这两个子集，每行一个子集，子集内元素以空格分隔。 * 如果不存在这样的子集，则输出一行 "Impossible"。 如果存在多组答案，输出任意一组均可。注意原题样例没有输出方案。

**限制条件** - $\mathbf{S}$ 中不会有相同的数。 - $1 \leq \mathbf{T} \leq 10$。 **测试集 1（6 分，结果可见）** - 时间限制：~~60~~ 12 秒。 - $\mathbf{N}$ 恰好等于 $20$。 - $\mathbf{S}$ 中每个数均为小于 $10^5$ 的正整数。 **测试集 2（37 分，结果隐藏）** - 时间限制：~~120~~ 30 秒。 - $\mathbf{N}$ 恰好等于 $500$。 - $\mathbf{S}$ 中每个数均为小于 $10^{12}$ 的正整数。 翻译由 ChatGPT-4.1 完成。