Problem1102--PIPI学加法

1102: PIPI学加法

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 694  Solved: 331
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI现在有一个数字 t, 和一个长度为 n 的正整数数组, 从数组中找到所有的不同的加法方式,在数组中选定元素之和为 t . 每个组合中数组元素只能使用一次。
举例: t=4, n=6, list = [4,3,2,2,1,1]
那么会有四种不同的选择方式让元素和为 t。
即 4: 4,3+1,2+2, 和 2+1+1.

Input

输入包含多组样例。
每组样例,第一行包含两个整数 t ,n (0<t<=1000, 1<= n <=12)。
第二行包含n个不超过100的正整数。
t=n=0时标志输入结束

Output

对于每组测试用例,
第一行输出"Sums of t:"
紧接着输出其不同的加法方式,按照答案中每个位置的值从大到小输出;若没有一种加法方式输出 NONE ,具体见输出样例。

Sample Input

4 6 
4 3 2 2 1 1
5 3 
2 1 1
480 12 
22 57 74 66 96 37 66 21 43 86 36 57

Sample Output

Sums of 4:
4
3+1
2+2
2+1+1
Sums of 5:
NONE
Sums of 480:
96+86+74+66+57+43+37+21
96+86+74+66+57+43+36+22
96+74+66+66+57+57+43+21
96+66+66+57+57+43+37+36+22

Source/Category