2025 B卷 100分 題型
本專欄內全部題目均提供Java、python、JavaScript、C、C++、GO六種語言的最佳實現方式；
并且每種語言均涵蓋詳細的問題分析、解題思路、代碼實現、代碼詳解、3個測試用例以及綜合分析；
本文收錄于專欄：《2025華為OD真題目錄+全流程解析+備考攻略+經驗分享》
華為OD機試真題《小明減肥》：
文章快捷目錄
題目描述及說明
Java
python
JavaScript
C++
C
GO
題目名稱：小明減肥
- 知識點：組合數學、回溯/枚舉
- 時間限制：1秒
- 空間限制：256MB
- 限定語言：不限
題目描述
小明有n個可選運動，每個運動對應一個卡路里值。他需要從中選出k個運動，使得這些運動的卡路里總和恰好為t。給定n、k、t及每個運動的卡路里列表，求可行的方案數量。
輸入描述
- 第一行輸入三個整數：
n（運動數量，0 < n < 10）、t（目標卡路里總和，t > 0）、k（需選的運動數，0 < k ≤ n）。 - 第二行輸入
n個正整數，表示每個運動的卡路里值（均 > 0），以空格分隔。
輸出描述
輸出滿足條件的方案數量（整數）。
示例
輸入：
4 3 2
1 1 2 3
輸出：
2
解釋：可選方案為[1,2]和[1,2]（注意重復卡路里值的不同索引視為不同方案）。
Java
問題分析
小明需要從n個運動中選擇k個，使得它們的卡路里總和恰好為t。我們需要計算所有符合條件的組合數量。每個運動的卡路里值可能重復，但不同索引視為不同方案。
解題思路
- 回溯枚舉：遍歷所有可能的k元素組合，統計滿足條件的方案數。
- 剪枝優化：在遞歸過程中，若已選元素超過k或總和超過t，提前終止該路徑。
- 索引處理：通過限定遍歷起始索引，確保生成的組合是無序且不重復的。
代碼實現
import java.util.Scanner;public class Main {private static int n; // 運動總數private static int t; // 目標卡路里總和private static int k; // 需要選的運動數private static int[] calories; // 各運動卡路里值數組private static int result = 0; // 合法方案計數器public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 讀取輸入參數n = scanner.nextInt();t = scanner.nextInt();k = scanner.nextInt();calories = new int[n];for (int i = 0; i < n; i++) {calories[i] = scanner.nextInt();}scanner.close();// 調用回溯函數，初始狀態：從索引0開始，已選0個，總和0backtrack(0, 0, 0);System.out.println(result);}/*** 回溯函數，遞歸遍歷所有可能的運動組合* @param start 當前處理的起始索引（避免重復組合）* @param count 已選的運動數目* @param sum 當前卡路里總和*/private static void backtrack(int start, int count, int sum) {// 剪枝：已選數目超過k，或總和超過t，直接返回if (count > k || sum > t) {return;}// 找到k個元素組合，判斷是否符合總和要求if (count == k) {if (sum == t) {result++; // 符合條件，計數器加一}return; // 無論是否符合，均停止遞歸}// 遍歷當前可選的索引范圍 [start, n-1]for (int i = start; i < n; i++) {// 選擇當前元素，遞歸處理下一個索引backtrack(i + 1, count + 1, sum + calories[i]);}}
}
代碼解析
-
輸入處理
- 讀取
n、t、k和卡路里數值數組，存入對應變量。
- 讀取
-
回溯函數
backtrack- 參數說明：
start確保組合按索引遞增生成避免重復；count記錄已選元素數量；sum記錄當前總和。 - 剪枝條件：若當前路徑已不可能滿足條件（數量超限或總和超限），提前終止。
- 終止條件：當已選元素等于
k時，檢查總和是否等于t并更新計數器。 - 循環遍歷：從
start開始依次選擇元素，遞歸處理后續元素。
- 參數說明：
示例測試
-
輸入示例1
4 3 2 1 1 2 3輸出：
2
解析：選擇第0、2元素（1+2）和第1、2元素（1+2）。 -
輸入示例2
3 5 2 2 3 4輸出：
1
解析：只有組合（2,3）滿足和為5。 -
輸入示例3
5 10 3 2 2 3 3 4輸出：
1
解析：組合（3,3,4）符合和為10。
綜合分析
-
時間復雜度
- 最壞情況為O(C(n,k))，例如取k個元素的組合數。由于n<10，實際運算量極小。
-
空間復雜度
- 遞歸棧深度為k，復雜度O(k)。卡路里數組存儲為O(n)。
-
正確性保障
- 索引遞增：避免重復組合，確保每個組合的唯一性。
- 剪枝優化：提前終止無效路徑，提升效率。
-
方案優勢
- 簡潔高效：遞歸結構清晰，適用于小規模數據。
- 無重復計算：通過索引遞增生成組合，確保每個組合只處理一次。
-
適用場景
- 需要枚舉組合的小規模問題（如n≤10），例如算法競賽或數據分析。
python
問題分析
小明需要從n個運動中選擇k個，使其卡路里總和恰好為t。我們需要統計所有滿足條件的組合數量，不同索引的同值卡路里視為不同方案。
解題思路
- 回溯枚舉：遍歷所有可能的k元素組合，統計滿足條件的方案數。
- 剪枝優化：在遞歸過程中，若已選元素超過k或總和超過t，提前終止該路徑。
- 索引遞增策略：通過固定選擇順序避免重復組合。
代碼實現
n, t, k = map(int, input().split())
calories = list(map(int, input().split()))
result = 0def b
)