Skip to content

1303: Subset sum

题目

题目描述

从 $n$ 个可能有重复的数字中取出一个非空子集,有 $2^n - 1$ 种取法。其中,每个数在 $2^{n-1}$ 个子集中出现。

现在给你 $2^n-1$ 个数,请构造 $n$ 个整数,使得他们的非空子集的和与这 $2^n - 1$ 个数对应相同。

Input

请从 stdin 读入。

输入第一行一个正整数 $n (1 \leq n \leq 15)$ 。

第二行包含 $ 2^n - 1$ 个空格隔开的整数,第 $i$ 个数为 $s_i (-10^6 \leq s_i \leq 10 ^ 6 )$。

对于 $50$ 分的数据,所有输入的数值的绝对值不大于 $5$。

Output

输出第一行,如果有解,输出 YES,否则输出 NO

如果有解,那么第二行为 $n$ 个空格隔开的整数,表示你的答案。

如果有多种方案,输出任意一种即可。

Sample Input

txt 2 1 2 3

txt 2 1 2 4

txt 3 0 1 -1 0 1 -1 0

Sample Output

txt YES 1 2

txt NO

txt YES 0 1 -1

Constraints

Time Limit: 1s

Memory Limit: 128MB

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!