华为OD机试_2025 B卷_小明减肥（Python，100分）（附详细解题思路）
题目描述
小明有n个可选运动，每个运动有对应卡路里，想选出其中k个运动且卡路里和为t。k，t，n都是给定的。求出可行解数量
输入描述
第一行输入n t k
第二行输入 每个运动的卡路里 按照空格进行分割
备注
0<n<10
t>0，0<k<=n
每个运动量的卡路里>0
输出描述
求出可行解数量
用例
| 输入 | 4 3 2 |
| 输出 | 2 |
| 说明 | 可行解为2，选取{0,2},{1,2}两种方式。 |
选k个运动卡路里和为t：组合枚举解法详解
核心解题思路
题目要求从n个运动中选择k个运动，使其卡路里之和恰好等于给定的目标值t。例如输入4 3 2和卡路里数组1 1 2 3时，有效的组合有(1,2)和(1,2)两种（选择索引0和2，或1和2）。
关键洞察：由于n<10（最多10个运动），我们可以使用组合枚举的方法：
- 生成所有可能的k个运动的组合
- 计算每个组合的卡路里总和
- 统计总和等于t的组合数量
这种方法时间复杂度可控（最大252种组合），实现简单直观。
解题步骤详解
1. 输入处理与参数设置
# 读取第一行：n, t, k
n, t, k = map(int, input().split())
# 读取第二行：卡路里数组
calories = list(map(int, input().split()))
2. 枚举所有k个运动的组合
使用Python标准库itertools.combinations生成所有可能的k个运动的组合：
from itertools import combinations# 生成所有k个元素的组合
all_combos = combinations(calories, k)
3. 计算组合总和并统计
遍历每个组合，计算卡路里和，检查是否等于t：
count = 0
for combo in all_combos:if sum(combo) == t: # 检查总和是否匹配count += 1
4. 输出结果
print(count) # 输出满足条件的组合数量
完整代码实现
import itertoolsdef main():# 读取输入n, t, k = map(int, input().split())calories = list(map(int, input().split()))# 枚举组合并统计count = 0for combo in itertools.combinations(calories, k):if sum(combo) == t:count += 1print(count)if __name__ == "__main__":main()
关键逻辑解析
1. 组合生成原理
itertools.combinations(calories, k)生成所有不重复的k元素组合：
- 输入
[1,1,2,3], k=2时生成：
(1,1),(1,2),(1,3),(1,2),(1,3),(2,3) - 注意：即使元素值相同（如两个1），不同索引被视为不同元素
2. 求和与条件检查
对每个组合直接计算总和：
sum(combo) # 如(1,2)的和为3
为什么不需要全排列？
因为卡路里和与顺序无关，(1,2)和(2,1)的和相同，组合枚举避免了重复计算。
3. 计数机制
每个满足sum(combo)==t的组合独立计数，即使元素值相同（如示例中的两个1）也视为不同方案。
复杂度分析
- 组合数量：C(n,k) ≤ C(10,5)=252（最大情况）
- 单次操作：求和操作O(k)，k≤10
- 总时间复杂度：O(C(n,k)k) ≤ 25210=2520次操作，远低于现代计算机处理能力
- 空间复杂度：O(k)存储组合，非常高效
示例验证
示例1：
输入：
4 3 2
1 1 2 3
处理流程：
- 生成6种组合：
(1,1)→2, (1,2)→3✅, (1,3)→4,
(1,2)→3✅, (1,3)→4, (2,3)→5 - 统计满足sum=3的组合：2个
输出：2
示例2：
输入：
5 10 3
2 3 5 7 9
处理流程：
- 生成C(5,3)=10种组合
- 检查到(2,3,5)=10✅, (3,5,2)=10✅（同一组合）
- 其他组合如(2,3,7)=12≠10
输出：1（只有一种组合满足）
总结
通过组合枚举法，我们高效解决了"选k个运动卡路里和为t"的问题：
- 适用条件：n较小时（n<20）的理想解法
- 优势：代码简洁（<10行核心逻辑），无需复杂算法
- 扩展性：若n较大可改用动态规划，但本题无需
- 核心技巧：利用
itertools.combinations生成组合，直接求和比较
对于初学者，掌握这种枚举思想是解决组合类问题的基石。当遇到类似"选择满足条件的子集"问题时，首先评估数据规模，小规模数据优先考虑枚举解法。