Problem2854--相加求和

2854: 相加求和

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Status] [Submit] [Creator:]

Description

给定一个整数t,和一个有n个数的整数序列,使用序列中的数找到一些数字的和刚好等于t。例如:t=4,n=6,整数序列为{4,3,2,2,1,1},那么一共有4种不同的求和使得结果等于4,分别是:4,3+1,2+2,2+1+1(一个数字在序列中出现过几次就能够被使用几次)。你的任务是找到满足条件的所有组合。

Input

输入包含多组测试数据,每组测试数据占一行。
第一个整数是t(t<1000)表示求和的结果,第二个整数是n(1≤n≤12)表示整数序列中数字的个数。接下来n个数分别表示序列中的n个整数,每个整数是不超过100的正整数。
当输入为一行"0 0"时,表示输入结束。

Output

对于每组测试数据,先输出一行"Sums of x:"其中x即为t的值,
接下来每行输出一个满足条件的求和,如果没有满足条件的求和则输出"NONE".
如果有多个求和表达式满足条件,则按照字典序递减顺序输出。在每个求和表达式中数字出现的顺序要满足是非递增的。

Sample Input Copy

4 6 4 3 2 2 1 1
5 3 2 1 1
400 12 50 50 50 50 50 50 25 25 25 25 25 25
0 0

Sample Output Copy

Sums of 4:
4
3+1
2+2
2+1+1
Sums of 5:
NONE
Sums of 400:
50+50+50+50+50+50+25+25+25+25
50+50+50+50+50+25+25+25+25+25+25

Source/Category