2025 A卷 100分 题型

本文涵盖详细的问题分析、解题思路、代码实现、代码详解、测试用例以及综合分析；
并提供Java、python、JavaScript、C++、C语言、GO六种语言的最佳实现方式！

2025华为OD真题目录+全流程解析/备考攻略/经验分享

华为OD机试真题《硬件产品销售方案》：

---

---

题目名称：硬件产品销售方案

---

维度	描述
知识点	回溯算法（DFS）、剪枝优化、排序预处理
时间限制	1秒
空间限制	256MB
限定语言	不限

---

题目描述

某公司推出多种硬件产品，每种产品包含若干型号且价格唯一。现需为合作厂商列出所有总金额等于 amount 元的产品组合。已知产品库存充足，且价格列表 price 中的元素互不相同。

输入描述

• 第一行为正整数 amount，表示采购金额。
• 第二行为逗号分隔的正整数列表 price，表示各型号的价格。

输出描述

• 输出所有可能的组合列表，格式为二维数组。若无法组合，返回空列表。
• 注意：组合中元素的顺序不同视为不同方案（如 [100, 200] 和 [200, 100] 视为两种组合），但实际题目中因允许重复选择同一产品，需按顺序枚举。

示例1
输入：

500  
100,200,300,500  

输出：

[[100,100,100,100,100], [100,100,100,200], [100,100,300], [100,200,200], [200,300], [500]]  

示例2
输入：

100  
100  

输出：

---

Java

问题分析

我们需要找到所有可能的价格组合，使得它们的总和等于给定的金额。每个价格可以重复使用，且组合中的元素顺序不同视为不同方案。为避免重复组合，需按非降序排列生成组合。

解题思路

1. 排序预处理：将价格数组排序，确保组合按非降序生成。
2. 回溯算法（DFS）：递归遍历所有可能的组合，记录满足条件的组合。
3. 剪枝优化：当当前路径的和超过目标金额时，停止进一步搜索。

代码实现

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int amount = Integer.parseInt(sc.nextLine());String[] prices = sc.nextLine().split(",");List<Integer> priceList = new ArrayList<>();for (String p : prices) {priceList.add(Integer.parseInt(p.trim()));}// 排序以便后续剪枝和去重Collections.sort(priceList);List<List<Integer>> result = new ArrayList<>();backtrack(priceList, amount, 0, new ArrayList<>(), 0, result);// 输出格式化System.out.println(formatResult(result));}/*** 回溯函数，递归生成所有可能的组合* @param prices   排序后的价格列表* @param target   目标金额* @param start    当前遍历的起始索引（避免重复组合）* @param path     当前路径（组合）* @param sum      当前路径的和* @param result   结果集*/private static void backtrack(List<Integer> prices, int target, int start, List<Integer> path, int sum, List<List<Integer>> result) {if (sum > target) return;      // 剪枝：总和超过目标，停止递归if (sum == target) {          // 找到有效组合，加入结果集result.add(new ArrayList<>(path));return;}// 从start开始遍历，避免生成重复组合for (int i = start; i < prices.size(); i++) {int price = prices.get(i);if (sum + price > target) break; // 剪枝：后续元素更大，无需继续path.add(price);                  // 将当前元素加入路径backtrack(prices, target, i, path, sum + price, result);path.remove(path.size() - 1);     // 回溯：移除当前元素}}/*** 将结果列表格式化为题目要求的字符串形式*/private static String formatResult(List<List<Integer>> result) {if (result.isEmpty()) return "[]";StringBuilder sb = new StringBuilder();sb.append("[");for (int i = 0; i < result.size(); i++) {sb.append("[");List<Integer> list = result.get(i);for (int j = 0; j < list.size(); j++) {sb.append(list.get(j));if (j < list.size() - 1) sb.append(",");}sb.append("]");if (i < result.size() - 1) sb.append(", ");}sb.append("]");return sb.toString();}
}

代码详细解析

1. 输入处理：读取金额和价格列表，将价格转换为整数并排序。
2. 回溯函数：
   • 终止条件：若当前和超过目标，直接返回；若等于目标，保存组合。
   • 循环遍历：从start索引开始遍历，避免重复组合。
   • 剪枝优化：若当前和加当前价格超过目标，终止后续循环。
3. 路径管理：递归前添加当前价格到路径，递归后移除（回溯）。
4. 结果格式化：将结果列表转换为符合题目要求的字符串格式。

示例测试

示例1输入：

500  
100,200,300,500  

输出：

[[100,100,100,100,100], [100,100,100,200], [100,100,300], [100,200,200], [200,300], [500]]

解析：

• 排序后价格为[100,200,300,500]。
• 通过回溯生成所有非降序组合，如[100×5]、[100×3+200]等。

示例2输入：

100  
100  

输出：

解析：

• 唯一可能的组合是[100]。

综合分析

1. 时间复杂度：最坏情况下为O(2^n)，但通过排序和剪枝优化，实际效率较高。
2. 空间复杂度：O(n)递归栈深度，结果存储空间为O(k·m)（k为组合数，m为平均组合长度）。
3. 优势：
   • 剪枝优化：通过排序和提前终止无效搜索，减少计算量。
   • 去重机制：通过固定遍历起点，避免生成重复组合。
4. 适用场景：适用于小规模数据（价格列表长度≤30），符合题目约束。

---

python

问题分析

我们需要找到所有可能的价格组合，使得它们的总和等于给定的金额。每个价格可以重复使用，且组合按非降序排列以避免重复。

解题思路

1. 排序预处理：将价格数组排序，确保组合按非降序生成。
2. 回溯算法（DFS）：递归遍历所有可能的组合，记录满足条件的组合。
3. 剪枝优化：当当前路径的和超过目标金额时，停止进一步搜索。

代码实现

def main():amount = int(input())prices = list(map