題目

數(shù)碼城市有土地出售。待售的土地被劃分成若干塊，每一塊標(biāo)有一個價格。這里假設(shè)每塊土地只有兩塊相鄰的土地，除了開頭和結(jié)尾的兩塊是只有一塊鄰居的。每位客戶可以購買多塊連續(xù)相鄰的土地。

現(xiàn)給定這一系列土地的標(biāo)價，請你編寫程序，根據(jù)客戶手頭的現(xiàn)金量，告訴客戶有多少種不同的購買方案。

輸入格式：
輸入首先在第一行給出兩個正整數(shù)：N（≤10
4
）為土地分割的塊數(shù)（于是這些塊從 1 到 N 順次編號）；M（≤10
9
）為客戶手中的現(xiàn)金量。

隨后一行給出 N 個正整數(shù)，其中第 i 個數(shù)字就是第 i 塊土地的標(biāo)價。

題目保證所有土地的總價不超過 10
9
。

輸出格式：
在一行中輸出客戶有多少種不同的購買方案。請注意客戶只能購買連續(xù)相鄰的土地。

輸入樣例：
5 85
38 42 15 24 9
結(jié)尾無空行
輸出樣例：
11
結(jié)尾無空行
樣例解釋：
這 11 種不同的方案為：

38
42
15
24
9
38 42
42 15
42 15 24
15 24
15 24 9
24 9

解題思路

N, maxZijin = map(int, input().split())
inputList = list(map(int, input().split()))
# N, maxZijin = map(int, "5 85".split())
# inputList = list(map(int, "38 42 15 24 9".split()))

ans = []
def dfs(idx:int, cur:int, patch:[int]):
    #遞歸結(jié)束
    if cur <= 0:
        # ans.append(patch[:])
        return
    elif idx == len(inputList):
        return
    if cur >= inputList[idx]:
        if len(patch) == 0 or idx==(patch[-1]+1):
            # print(idx, cur, patch,inputList[idx])
            # print(idx, cur, patch)
            # and (idx == (patch[-1] + 1))
            patch.append(idx)
            ans.append(patch[:])
            dfs(idx+1, cur - inputList[idx] ,patch)
            # return
            #消除影響【重要】
            patch.pop()
    dfs(idx + 1, cur, patch)

dfs(0,maxZijin,[])
print(len(ans))