Sum It Up ## 来源 Mid-Central USA 1997 (ZOJ1711, POJ1564) ## 题目描述 给定一个总和t，以及n个整数，从这n个整数中选取若干个，使得和为t。求所有满足这个条件的组合情况。例如，假设t = 4，n = 6，这6个整数为：[4，3，2，2，1，1]。这6个整数中，有4个不同的组合，满足和为4：4，3+1，2+2，2+1+1。注意：同一个整数在一个组合中可以出现多次，只要不超过它在整数列表中出现的次数；一个整数也可以单独成为一个组合。 ## 输入描述 输入文件中包含多个测试数据。每个测试数据占一行：首先是总和t；接下来是整数n，表示整数的个数；最后是n个整数：x1，...，xn。如果n = 0，则表示输入结束。否则，t为正整数，且t<1000，n的值满足：1≤n≤12，x1，...，xn均为小于100的正整数。测试数据中所有数都是用空格隔开的。每个测试数据中的n个整数是以非递增的顺序排列的，允许有重复的数据。 ## 输出描述 对每个测试数据，首先输出一行，格式为“Sums of t：”，t为测试数据中的总和t。然后输出所有满足要求的组合，每个组合占一行，如果没有满足要求的组合，则仅输出“NONE”。组合中的正整数以非递增的顺序排列。组合以在其中出现的整数的降序排列，也就是说，首先按第一个数的降序排序，第1个数相同则按第2个数的降序排序，以此类推。在每个测试数据中，各个组合必须互不相同，不能重复输出。 ## 样例输入 ```txt 4 6 4 3 2 2 1 1 5 3 2 1 1 0 0 ``` ## 样例输出 ```txt Sums of 4: 4 3+1 2+2 2+1+1 Sums of 5: NONE ```