餐厅点菜

题目描述

餐厅里有n种菜，第i中卖pi元，每种菜最多只能点一份。现在打算花光m元。请问有几种点菜方式？

输入描述

输入共2行：

第1行，2个正整数n，n，以空格隔开。

第2行，n个正整数p1，p2，p3，...，pn，以空格隔开。

输出描述

一个正整数，表示点菜方式的种树

样例输入

4 5

1 2 3 4

样例输出

2

代码详解

展开查看

n,m = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
use = [False for i in range(n)]
cnt = 0

def dfs(step):
    global n,m,p,use,cnt
    if step >= n:
        to = 0
        for i in range(n):
            if use[i] == True:
                to += p[i]
        if to == m:
            cnt += 1
        return
    use[step] = False
    dfs(step+1)
    use[step] = True
    dfs(step+1)

dfs(0)
print(cnt)

运行结果

展开查看

4 5
1 2 3 4
2