华为OD机试真题——硬件产品销售方案（2025A卷：100分）Java/python/JavaScript/C++/C语言/GO六种最佳实现
2025 A卷 100分 题型
本文涵盖详细的问题分析、解题思路、代码实现、代码详解、测试用例以及综合分析；
并提供Java、python、JavaScript、C++、C语言、GO六种语言的最佳实现方式！
2025华为OD真题目录+全流程解析/备考攻略/经验分享
华为OD机试真题《硬件产品销售方案》：
目录
- 题目名称：硬件产品销售方案
- 题目描述
- Java
- 问题分析
- 解题思路
- 代码实现
- 代码详细解析
- 示例测试
- 示例1输入：
- 示例2输入：
- 综合分析
- python
- 问题分析
- 解题思路
- 代码实现
- 代码详细解析
- 示例测试
- 示例1输入：
- 示例2输入：
- 综合分析
- JavaScript
- 问题分析
- 解题思路
- 代码实现
- 代码详细解析
- 示例测试
- 示例1输入：
- 示例2输入：
- 综合分析
- C++
- 问题分析
- 解题思路
- 代码实现
- 代码详细解析
- 示例测试
- 示例1输入：
- 示例2输入：
- 综合分析
- C语言
- 问题分析
- 解题思路
- 代码实现
- 代码详细解析
- 示例测试
- 示例1输入：
- 示例2输入：
- 综合分析
- GO
- 问题分析
- 解题思路
- 代码实现
- 代码详细解析
- 1. 输入处理
- 2. 回溯函数
- 3. 结果格式化
- 示例测试
- 示例1输入：
- 示例2输入：
- 综合分析
- 扩展
- 更多内容：
题目名称：硬件产品销售方案
| 维度 | 描述 |
|---|---|
| 知识点 | 回溯算法（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
问题分析
我们需要找到所有可能的价格组合，使得它们的总和等于给定的金额。每个价格可以重复使用，且组合中的元素顺序不同视为不同方案。为避免重复组合，需按非降序排列生成组合。
解题思路
- 排序预处理：将价格数组排序，确保组合按非降序生成。
- 回溯算法（DFS）：递归遍历所有可能的组合，记录满足条件的组合。
- 剪枝优化：当当前路径的和超过目标金额时，停止进一步搜索。
代码实现
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();}
}
代码详细解析
- 输入处理：读取金额和价格列表，将价格转换为整数并排序。
- 回溯函数：
- 终止条件：若当前和超过目标，直接返回；若等于目标，保存组合。
- 循环遍历：从
start索引开始遍历，避免重复组合。 - 剪枝优化：若当前和加当前价格超过目标，终止后续循环。
- 路径管理：递归前添加当前价格到路径，递归后移除（回溯）。
- 结果格式化：将结果列表转换为符合题目要求的字符串格式。
示例测试
示例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]。
综合分析
- 时间复杂度：最坏情况下为O(2^n)，但通过排序和剪枝优化，实际效率较高。
- 空间复杂度：O(n)递归栈深度，结果存储空间为O(k·m)（k为组合数，m为平均组合长度）。
- 优势：
- 剪枝优化：通过排序和提前终止无效搜索，减少计算量。
- 去重机制：通过固定遍历起点，避免生成重复组合。
- 适用场景：适用于小规模数据（价格列表长度≤30），符合题目约束。
python
问题分析
我们需要找到所有可能的价格组合，使得它们的总和等于给定的金额。每个价格可以重复使用，且组合按非降序排列以避免重复。
解题思路
- 排序预处理：将价格数组排序，确保组合按非降序生成。
- 回溯算法（DFS）：递归遍历所有可能的组合，记录满足条件的组合。
- 剪枝优化：当当前路径的和超过目标金额时，停止进一步搜索。
代码实现
def main():amount = int(input())prices = list(map(int, input().strip().split(',')))prices.sort()result = []def backtrack(start, path, current_sum):if current_sum == amount:result.append(path.copy())returnfor i in range(start, len(prices)):price = prices[i]if current_sum + price > amount:break # 剪枝：后续价格更大，无需继续path.append(price)backtrack(i, path, current_sum + price)path.pop()backtrack(0, [], 0)print(format_result(result))def format_result(result):if not result:return "[]"formatted = []for combo in result:formatted.append("[{}]".format(",".join(map(str, combo))))return "[{}]".format(", ".join(formatted))if __name__ == "__main__":main()
代码详细解析
- 输入处理：读取金额和价格列表，转换为整数并排序。
- 回溯函数：
- 终止条件：若当前和等于目标金额，保存组合。
- 循环遍历：从
start索引开始，保证组合非降序。 - 剪枝优化：若当前和加当前价格超过目标，终止循环。
- 路径管理：递归前添加价格到路径，递归后移除（回溯）。
- 结果格式化：将结果转换为题目要求的二维数组格式。
示例测试
示例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]。
综合分析
- 时间复杂度：最坏情况下为O(2ⁿ)，但通过剪枝优化，实际效率较高。
- 空间复杂度：O(n)递归栈深度，结果存储为O(k·m)（k为组合数，m为平均组合长度）。
- 优势：
- 剪枝优化：通过排序提前终止无效搜索。
- 去重机制：固定遍历起点，保证组合非降序。
- 适用场景：适用于小规模数据（价格列表长度≤30）。
JavaScript
问题分析
我们需要找到所有可能的价格组合，使得它们的总和等于给定的金额。每个价格可以重复使用，组合需按非降序排列以避免重复。
解题思路
- 排序预处理：将价格数组排序，确保组合按非降序生成。
- 回溯算法（DFS）：递归遍历所有可能的组合，记录满足条件的组合。
- 剪枝优化：当当前路径的和超过目标金额时，停止进一步搜索。
代码实现
const readline = require('readline');const rl = readline.createInterface({input: process.stdin,output: process.stdout,terminal: false
});let lines = [];
rl.on('line', (line) => {lines.push(line.trim());
}).on('close', () => {const amount = parseInt(lines[0]);const prices = lines[1].split(',').map(Number).sort((a, b) => a - b);const result = [];// 回溯函数定义const backtrack = (start, path, currentSum) => {if (currentSum === amount) {result.push([...path]); // 存储路径副本return;}for (let i = start; i < prices.length; i++) {const price = prices[i];if (currentSum + price > amount) break; // 剪枝：超过目标金额path.push(price); // 添加当前价格backtrack(i, path, currentSum + price); // 递归探索path.pop(); // 回溯：移除最后添加的价格}};backtrack(0, [], 0); // 初始调用console.log(formatResult(result)); // 格式化输出
});// 结果格式化函数
const formatResult = (result) => {if (result.length === 0) return '[]';const formatted = result.map(combo => `[${combo.join(',')}]`);return `[${formatted.join(', ')}]`;
};
代码详细解析
-
输入处理：
- 使用
readline模块读取两行输入，分别存储金额和价格列表。 - 将价格转换为数字数组并排序，确保后续生成非降序组合。
- 使用
-
回溯函数：
- 参数说明：
start：当前遍历的起始索引，避免重复组合。path：当前路径（组合）。currentSum：当前路径的价格总和。
- 终止条件：当
currentSum === amount时，将路径副本存入结果。 - 循环遍历：从
start开始，避免生成逆序组合。 - 剪枝优化：若当前价格导致总和超限，终止后续循环。
- 路径管理：递归前添加价格，递归后弹出（回溯）。
- 参数说明：
-
结果格式化：
- 处理空结果返回
[]。 - 将每个组合转换为字符串格式，用逗号分隔元素。
- 处理空结果返回
示例测试
示例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]，直接命中目标金额。
综合分析
-
时间复杂度：O(2ⁿ)
- 最坏情况下需遍历所有组合，但通过剪枝大幅减少实际计算量。
- 示例1中有效剪枝：当
100×5=500后，跳过更大价格的无效路径。
-
空间复杂度：O(n²)
- 递归调用栈深度为 O(n)，结果存储空间为 O(k·m)，k为组合数，m为平均组合长度。
-
优势：
- 去重机制：通过固定遍历起点，保证组合非降序。
- 剪枝优化：提前终止无效路径，提升效率。
-
适用场景：
- 价格列表长度 ≤ 30 的中小规模数据。
- 需要精确枚举所有可能性的场景，如商品组合推荐。
C++
问题分析
我们需要找到所有可能的价格组合，使得它们的总和等于给定的金额。每个价格可以重复使用，组合需按非降序排列以避免重复。
解题思路
- 排序预处理：将价格数组排序，确保组合按非降序生成。
- 回溯算法（DFS）：递归遍历所有可能的组合，记录满足条件的组合。
- 剪枝优化：当当前路径的和超过目标金额时，停止进一步搜索。
代码实现
#include <iostream>
#include <vector>
#include <sstream>
#include <algorithm>using namespace std;void backtrack(const vector<int>& prices, int target, int start, vector<int>& path, int sum, vector<vector<int>>& result) {if (sum == target) {result.push_back(path);return;}for (int i = start; i < prices.size(); ++i) {if (sum + prices[i] > target) break; // 剪枝：后续价格更大，无需继续path.push_back(prices[i]); // 添加当前价格backtrack(prices, target, i, path, sum + prices[i], result);path.pop_back(); // 回溯：移除最后添加的价格}
}string formatResult(const vector<vector<int>>& result) {if (result.empty()) return "[]";stringstream ss;ss << "[";for (size_t i = 0; i < result.size(); ++i) {ss << "[";const auto& combo = result[i];for (size_t j = 0; j < combo.size(); ++j) {ss << combo[j];if (j != combo.size() - 1) ss << ",";}ss << "]";if (i != result.size() - 1) ss << ", ";}ss << "]";return ss.str();
}int main() {int amount;cin >> amount;cin.ignore(); // 忽略换行符string line;getline(cin, line);vector<int> prices;stringstream ss(line);string token;while (getline(ss, token, ',')) {prices.push_back(stoi(token));}sort(prices.begin(), prices.end()); // 排序以便剪枝和去重vector<vector<int>> result;vector<int> path;backtrack(prices, amount, 0, path, 0, result);cout << formatResult(result) << endl;return 0;
}
代码详细解析
-
输入处理：
cin >> amount读取金额。getline(cin, line)读取价格行，并用stringstream分割为整数数组。sort()对价格排序，确保后续生成非降序组合。
-
回溯函数：
- 参数说明：
prices：排序后的价格数组。target：目标金额。start：当前遍历的起始索引，避免生成逆序组合。path：当前路径（组合）。sum：当前路径的和。result：结果集。
- 终止条件：当
sum == target时，将路径存入结果。 - 剪枝优化：若当前价格导致总和超限，终止循环（
break）。 - 路径管理：递归前
push_back，递归后pop_back恢复状态。
- 参数说明：
-
结果格式化：
- 处理空结果返回
[]。 - 使用嵌套循环将每个组合转换为字符串，符合题目要求的二维数组格式。
- 处理空结果返回
示例测试
示例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]，直接命中目标金额。
综合分析
-
时间复杂度：O(2ⁿ)
- 最坏情况下需遍历所有组合，但通过剪枝大幅减少实际计算量。
- 示例1中剪枝跳过所有无效路径（如
100×6）。
-
空间复杂度：O(n²)
- 递归栈深度为 O(n)，结果存储空间为 O(k·m)，k为组合数，m为平均组合长度。
-
优势：
- 去重机制：固定遍历起点，保证组合非降序。
- 剪枝优化：提前终止无效路径，提升效率。
-
适用场景：
- 价格列表长度 ≤ 30 的中小规模数据。
- 需要精确枚举所有可能性的场景，如商品组合推荐。
C语言
问题分析
我们需要找到所有可能的价格组合，使得它们的总和等于给定的金额。每个价格可以重复使用，组合需按非降序排列以避免重复。
解题思路
- 排序预处理：将价格数组排序，确保组合按非降序生成。
- 回溯算法（DFS）：递归遍历所有可能的组合，记录满足条件的组合。
- 剪枝优化：当当前路径的和超过目标金额时，停止进一步搜索。
代码实现
#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 定义动态数组结构体（存储结果集）
typedef struct {int **data; // 二维数组存储组合int *sizes; // 每个组合的长度int capacity; // 当前分配的容量int size; // 实际元素数量
} ResultList;// 初始化结果集
ResultList* createResultList(int initialCapacity) {ResultList *list = malloc(sizeof(ResultList));list->data = malloc(initialCapacity * sizeof(int*));list->sizes = malloc(initialCapacity * sizeof(int));list->capacity = initialCapacity;list->size = 0;return list;
}// 向结果集中添加组合
void addToResult(ResultList *list, const int *path, int pathSize) {if (list->size >= list->capacity) { // 扩容list->capacity *= 2;list->data = realloc(list->data, list->capacity * sizeof(int*));list->sizes = realloc(list->sizes, list->capacity * sizeof(int));}// 复制路径数据int *newPath = malloc(pathSize * sizeof(int));memcpy(newPath, path, pathSize * sizeof(int));list->data[list->size] = newPath;list->sizes[list->size] = pathSize;list->size++;
}// 释放结果集内存
void freeResultList(ResultList *list) {for (int i = 0; i < list->size; i++) {free(list->data[i]);}free(list->data);free(list->sizes);free(list);
}// 回溯函数
void backtrack(int *prices, int pricesSize, int target, int start, int *path, int pathSize, int currentSum, ResultList *result) {if (currentSum == target) {addToResult(result, path, pathSize);return;}for (int i = start; i < pricesSize; i++) {if (currentSum + prices[i] > target) break; // 剪枝path[pathSize] = prices[i]; // 添加当前价格backtrack(prices, pricesSize, target, i, path, pathSize + 1, currentSum + prices[i], result);}
}// 比较函数（用于排序）
int compare(const void *a, const void *b) {return (*(int*)a - *(int*)b);
}// 格式化输出结果
void formatResult(ResultList *result) {if (result->size == 0) {printf("[]\n");return;}printf("[");for (int i = 0; i < result->size; i++) {printf("[");for (int j = 0; j < result->sizes[i]; j++) {printf("%d", result->data[i][j]);if (j != result->sizes[i] - 1) printf(",");}printf("]");if (i != result->size - 1) printf(", ");}printf("]\n");
}int main() {// 读取输入int amount;scanf("%d", &amount);getchar(); // 读取换行符char line[1000];fgets(line, sizeof(line), stdin);line[strcspn(line, "\n")] = '\0'; // 去除换行符// 分割字符串为价格数组int prices[100];int pricesSize = 0;char *token = strtok(line, ",");while (token != NULL) {prices[pricesSize++] = atoi(token);token = strtok(NULL, ",");}// 排序价格数组qsort(prices, pricesSize, sizeof(int), compare);// 初始化结果集和路径ResultList *result = createResultList(10);int *path = malloc(100 * sizeof(int)); // 路径最大长度设为100backtrack(prices, pricesSize, amount, 0, path, 0, 0, result);formatResult(result);// 释放内存free(path);freeResultList(result);return 0;
}
代码详细解析
- 动态数组结构体：
ResultList用于存储所有找到的组合，包含二维数组、各组合长度、容量和实际大小。 - 内存管理函数：
createResultList：初始化结果集，预分配内存。addToResult：动态扩容并复制路径数据。freeResultList：递归释放所有内存。
- 回溯函数：
- 通过
path数组记录当前组合，pathSize记录当前组合长度。 - 剪枝逻辑：若当前和超过目标，终止后续循环。
- 通过
- 输入处理：
- 用
fgets读取价格行，分割为整数数组。 - 使用
qsort对价格排序。
- 用
- 格式化输出：遍历结果集，按题目要求拼接字符串。
示例测试
示例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]，直接命中目标金额。
综合分析
- 时间复杂度：O(2ⁿ)
- 最坏情况需遍历所有组合，剪枝大幅减少实际计算量。
- 空间复杂度：O(k·m)
- 结果集存储所有组合，k为组合数，m为平均组合长度。
- 优势：
- 手动内存管理：精准控制内存分配，适合嵌入式场景。
- 高效剪枝：通过排序和提前终止优化性能。
- 适用场景：
- 需要严格内存控制的系统。
- 中小规模数据（价格数量≤100）。
GO
问题分析
我们需要找到所有可能的价格组合，使得它们的总和等于给定的金额。每个价格可以重复使用，组合需按非降序排列以避免重复。例如，给定金额 500 和价格列表 [100,200,300,500]，组合 [100,100,300] 是有效的，而 [300,100,100] 被视为重复。
解题思路
- 排序预处理：将价格数组排序，确保后续生成的组合按非降序排列。
- 回溯算法（DFS）：递归遍历所有可能的组合，记录满足条件的组合。
- 剪枝优化：当当前路径的和超过目标金额时，停止进一步搜索。
- 路径管理：通过切片动态管理当前路径，回溯时恢复状态。
代码实现
package mainimport ("bufio""fmt""os""sort""strconv""strings"
)func main() {// 读取输入scanner := bufio.NewScanner(os.Stdin)scanner.Scan()amount, _ := strconv.Atoi(scanner.Text())scanner.Scan()pricesStr := strings.Split(scanner.Text(), ",")// 转换为整数并排序prices := make([]int, len(pricesStr))for i, s := range pricesStr {prices[i], _ = strconv.Atoi(strings.TrimSpace(s))}sort.Ints(prices)// 回溯搜索var result [][]intbacktrack(prices, amount, 0, []int{}, 0, &result)// 格式化输出fmt.Println(formatResult(result))
}// 回溯函数
func backtrack(prices []int, target, start int, path []int, sum int, result *[][]int) {if sum == target {// 深拷贝当前路径，避免后续修改影响结果newPath := make([]int, len(path))copy(newPath, path)*result = append(*result, newPath)return}for i := start; i < len(prices); i++ {price := prices[i]if sum+price > target {break // 剪枝：后续价格更大，无需继续}// 添加当前价格到路径path = append(path, price)backtrack(prices, target, i, path, sum+price, result)// 回溯：移除最后添加的价格path = path[:len(path)-1]}
}// 结果格式化函数
func formatResult(result [][]int) string {if len(result) == 0 {return "[]"}str := "["for i, combo := range result {str += "["for j, num := range combo {str += strconv.Itoa(num)if j < len(combo)-1 {str += ","}}str += "]"if i < len(result)-1 {str += ", "}}str += "]"return str
}
代码详细解析
1. 输入处理
scanner := bufio.NewScanner(os.Stdin)
scanner.Scan()
amount, _ := strconv.Atoi(scanner.Text())
- 使用
bufio.Scanner逐行读取输入。 - 第一行转换为整数金额
amount。
pricesStr := strings.Split(scanner.Text(), ",")
prices := make([]int, len(pricesStr))
for i, s := range pricesStr {prices[i], _ = strconv.Atoi(strings.TrimSpace(s))
}
sort.Ints(prices)
- 第二行分割为字符串数组，转换为整数切片。
- 对价格排序，确保后续生成非降序组合。
2. 回溯函数
func backtrack(prices []int, target, start int, path []int, sum int, result *[][]int) {if sum == target {newPath := make([]int, len(path))copy(newPath, path)*result = append(*result, newPath)return}// 循环逻辑...
}
- 参数说明：
prices：排序后的价格列表。target：目标金额。start：当前搜索的起始索引（避免重复组合）。path：当前路径（组合）。sum：当前路径的总和。result：存储结果的切片指针。
for i := start; i < len(prices); i++ {price := prices[i]if sum+price > target {break // 剪枝}path = append(path, price)backtrack(prices, target, i, path, sum+price, result)path = path[:len(path)-1] // 回溯
}
- 剪枝逻辑：若当前价格导致总和超限，终止后续循环。
- 路径管理：递归前添加价格到路径，递归后移除（回溯）。
3. 结果格式化
func formatResult(result [][]int) string {// 拼接字符串逻辑...
}
- 处理空结果返回
[]。 - 使用嵌套循环将每个组合转换为目标格式的字符串。
示例测试
示例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]。 - 递归过程：
- 选择
1005次 →[100×5]。 - 选择
1003次后选200→[100×3,200]。 - 其他组合类似，最终输出所有非降序组合。
- 选择
示例2输入：
100
100
输出：
解析：
- 唯一可能的组合是
[100]，直接命中目标金额。
综合分析
-
时间复杂度：
- 最坏情况：O(2ⁿ)，其中 n 为价格列表长度。
- 剪枝优化后：实际运行时间远小于理论值，例如示例1中跳过所有
price > 500的路径。
-
空间复杂度：
- 递归栈：O(n)，取决于价格列表长度。
- 结果存储：O(k·m)，k 为组合数，m 为平均组合长度。
-
优势：
- 避免重复组合：通过排序和固定起始索引
start实现。 - 内存高效：Go 的切片动态扩容机制减少内存浪费。
- 避免重复组合：通过排序和固定起始索引
-
适用场景：
- 价格数量 ≤ 100 的中小规模数据。
- 需要精确枚举所有可能性的场景（如商品推荐系统）。
扩展
Go语言特性带来的优势：
- 切片动态管理：无需手动处理数组扩容，简化代码。
- 值传递与指针：通过指针传递结果切片，避免深拷贝开销。
- 内置排序函数：
sort.Ints一行代码完成排序。
潜在改进方向：
- 并行计算：利用
goroutine分割搜索空间，加速大规模数据处理。 - 内存池优化：预分配结果切片内存，减少动态扩容次数。
- 字典树剪枝：对价格列表构建前缀树，进一步优化剪枝逻辑。
更多内容：
https://www.kdocs.cn/l/cvk0eoGYucWA
本文发表于【纪元A梦】，关注我，获取更多实用教程/资源！