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