题解 | #数字和为sum的方法数#

import sys

inputs = []
for line in sys.stdin:
    inputs.extend(list(map(int, line.split())))

def count_combinations(n, sum, nums):
    dp = [[0 for _ in range(sum + 1)] for _ in range(n + 1)]
    '''
    [
        [0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0],
    ]
    '''
    for i in range(n + 1):
        dp[i][0] = 1
        '''
        [
            [1, 0, 0, 0, 0, 0],
            [1, 0, 0, 0, 0, 0],
            [1, 0, 0, 0, 0, 0],
            [1, 0, 0, 0, 0, 0],
            [1, 0, 0, 0, 0, 0],
            [1, 0, 0, 0, 0, 0],
        ]
        '''
    for i in range(1, n + 1):
        # i = 1, 2, 3, 4, 5
        for j in range(1, sum + 1):
            # j = 1, 2, ..., 15
            if nums[i - 1] > j:
                # 5 > 1
                # dp[1][1] = dp[0][1]
                dp[i][j] = dp[i - 1][j]
            else:
                # dp[1][5] = dp[0][5] + dp[0][0]
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]]
    return dp[n][sum]

print(count_combinations(inputs[0], inputs[1], inputs[2:]))