题目
数码城市有土地出售。待售的土地被划分成若干块，每一块标有一个价格。这里假设每块土地只有两块相邻的土地，除了开头和结尾的两块是只有一块邻居的。每位客户可以购买多块连续相邻的土地。
现给定这一系列土地的标价，请你编写程序，根据客户手头的现金量，告诉客户有多少种不同的购买方案。
输入格式： 输入首先在第一行给出两个正整数：N（≤10 4 ）为土地分割的块数（于是这些块从 1 到 N 顺次编号）；M（≤10 9 ）为客户手中的现金量。
随后一行给出 N 个正整数，其中第 i 个数字就是第 i 块土地的标价。
题目保证所有土地的总价不超过 10 9 。
输出格式： 在一行中输出客户有多少种不同的购买方案。请注意客户只能购买连续相邻的土地。
输入样例： 5 85 38 42 15 24 9 结尾无空行 输出样例： 11 结尾无空行 样例解释： 这 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]): #递归结束 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))
