问题描述

给定目标总和$t$和一个包含$n$个整数的列表，找出列表中所有不同的数字组合，使其和等于$t$。

每个数字在组合中出现的次数不能超过其在列表中出现的次数，单个数字也可以作为组合。

示例说明

当输入为$t=4$，$n=6$，列表为$[4, 3, 2, 2, 1, 1]$时，存在四种满足条件的组合：

1. $4$
2. $3+1$
3. $2+2$
4. $2+1+1$

输入

• 多组测试数据，每组数据占一行
• 每行格式为：$t$ $n$ $x_1$ $x_2$ ... $x_n$
• 当$n=0$时输入结束
• 保证：
  • $t < 1000$
  • $1 \leq n \leq 12$
  • $x_i < 100$
• 列表中的数字按非递增顺序排列，可能存在重复值

输出

对每组测试数据：

1. 首行输出"Sums of $t$:"
2. 后续每行输出一个有效组合（数字按非递增顺序排列，用"$+$"连接）
3. 若无解则输出"NONE"
4. 组合按字典序从大到小排列（先比较第一个数字，再比较第二个数字，依此类推）
5. 重复组合只输出一次

输入数据1

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

输出数据1

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

来源

1997年美国中北部编程比赛