# 付款[2019北京市赛初中组T1] ## 题目描述 Lazy Jazz手上有n张钞票，每张钞票的面额分别是$M_i,(i \in [1,n])$ 请你以从小到大的顺序输出所有可能组成的金额 ## 输入格式 第一行包含一个正整数n 第二行包括由空格隔开的n个正整数，依次表示每张钞票的金额$M_i$ ## 输出格式 若干行，从小到大输出所有可能组合出的金额，每个金额数字占一行 ## 样例 #1 ### 样例输入 #1 ``` 6 1 1 1 1 5 10 ``` ### 样例输出 #1 ``` 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ``` ## 提示 1s，256M 对于50%的测试数据，n≤20 对于100%的测试数据，n≤100,$M_i ≤ 100$用

这道题和上一道问题的思路是一样的，只不过需要输出所有可能的组合，而不仅仅是组成的金额。我们可以用一个长度为sum+1的数组dp，其中dp[i]表示组成金额为i所需要的钞票数。初始时，我们将dp[0]赋为0，其他位置赋为正无穷大。

接下来，对于每一张面额为M_i的钞票，我们都可以选择使用或者不使用。如果使用了这张钞票，那么我们就需要在dp[M_i]到dp[sum]之间更新所有的状态，具体来说，dp[j] = min(dp[j], dp[j - M_i] + 1)。如果不使用这张钞票，那么状态不需要更新。

最终，所有dp[i]不为正无穷大的i就是所有可能组合出的金额，我们可以通过回溯来输出所有的组合方案。

下面是对应的Python代码实现：

n = int(input())
M = list(map(int, input().split()))
sum = 0
for i in range(n):
    sum += M[i]

dp = [float('inf')] * (sum + 1)
dp[0] = 0

for i in range(n):
    for j in range(M[i], sum + 1):
        dp[j] = min(dp[j], dp[j - M[i]] + 1)

for i in range(1, sum + 1):
    if dp[i] != float('inf'):
        print(i)

print("组合方案：")

def dfs(idx, cur_sum, path):
    if idx == n:
        if cur_sum in dp and dp[cur_sum] == len(path):
            print(path)
        return

    dfs(idx + 1, cur_sum, path)
    dfs(idx + 1, cur_sum + M[idx], path + [M[idx]])

dfs(0, 0, [])