华为OD机试真题——硬件产品销售方案（2025A卷：100分）Java/python/JavaScript/C++/C语言/GO六种最佳实现

2025 A卷 100分 题型

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

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

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

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

题目描述

某公司推出多种硬件产品，每种产品包含若干型号且价格唯一。现需为合作厂商列出所有总金额等于 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(int, input().strip().split(',')))
    prices.sort()
    result = []

    def backtrack(start, path, current_sum):
        if current_sum == amount:
            result.append(path.copy())
            return
        for 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()

代码详细解析

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ⁿ)，但通过剪枝优化，实际效率较高。
2. 空间复杂度：O(n)递归栈深度，结果存储为O(k·m)（k为组合数，m为平均组合长度）。
3. 优势：
   • 剪枝优化：通过排序提前终止无效搜索。
   • 去重机制：固定遍历起点，保证组合非降序。
4. 适用场景：适用于小规模数据（价格列表长度≤30）。

JavaScript

问题分析

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

解题思路

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

代码实现

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(', ')}]`;
};

代码详细解析

1. 输入处理：

   • 使用 readline 模块读取两行输入，分别存储金额和价格列表。
   • 将价格转换为数字数组并排序，确保后续生成非降序组合。

2. 回溯函数：

   • 参数说明：
     • start：当前遍历的起始索引，避免重复组合。
     • path：当前路径（组合）。
     • currentSum：当前路径的价格总和。
   • 终止条件：当 currentSum === amount 时，将路径副本存入结果。
   • 循环遍历：从 start 开始，避免生成逆序组合。
   • 剪枝优化：若当前价格导致总和超限，终止后续循环。
   • 路径管理：递归前添加价格，递归后弹出（回溯）。

3. 结果格式化：

   • 处理空结果返回 []。
   • 将每个组合转换为字符串格式，用逗号分隔元素。

示例测试

示例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ⁿ)

   • 最坏情况下需遍历所有组合，但通过剪枝大幅减少实际计算量。
   • 示例1中有效剪枝：当 100×5=500 后，跳过更大价格的无效路径。

2. 空间复杂度：O(n²)

   • 递归调用栈深度为 O(n)，结果存储空间为 O(k·m)，k为组合数，m为平均组合长度。

3. 优势：

   • 去重机制：通过固定遍历起点，保证组合非降序。
   • 剪枝优化：提前终止无效路径，提升效率。

4. 适用场景：

   • 价格列表长度 ≤ 30 的中小规模数据。
   • 需要精确枚举所有可能性的场景，如商品组合推荐。

C++

问题分析

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

解题思路

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

代码实现

#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;
}

代码详细解析

1. 输入处理：

   • cin >> amount 读取金额。
   • getline(cin, line) 读取价格行，并用 stringstream 分割为整数数组。
   • sort() 对价格排序，确保后续生成非降序组合。

2. 回溯函数：

   • 参数说明：
     • prices：排序后的价格数组。
     • target：目标金额。
     • start：当前遍历的起始索引，避免生成逆序组合。
     • path：当前路径（组合）。
     • sum：当前路径的和。
     • result：结果集。
   • 终止条件：当 sum == target 时，将路径存入结果。
   • 剪枝优化：若当前价格导致总和超限，终止循环（break）。
   • 路径管理：递归前 push_back，递归后 pop_back 恢复状态。

3. 结果格式化：

   • 处理空结果返回 []。
   • 使用嵌套循环将每个组合转换为字符串，符合题目要求的二维数组格式。

示例测试

示例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ⁿ)

   • 最坏情况下需遍历所有组合，但通过剪枝大幅减少实际计算量。
   • 示例1中剪枝跳过所有无效路径（如 100×6）。

2. 空间复杂度：O(n²)

   • 递归栈深度为 O(n)，结果存储空间为 O(k·m)，k为组合数，m为平均组合长度。

3. 优势：

   • 去重机制：固定遍历起点，保证组合非降序。
   • 剪枝优化：提前终止无效路径，提升效率。

4. 适用场景：

   • 价格列表长度 ≤ 30 的中小规模数据。
   • 需要精确枚举所有可能性的场景，如商品组合推荐。

C语言

问题分析

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

解题思路

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

代码实现

#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));  // 路径最大长度设为100
    
    backtrack(prices, pricesSize, amount, 0, path, 0, 0, result);
    formatResult(result);
    
    // 释放内存
    free(path);
    freeResultList(result);
    return 0;
}

代码详细解析

1. 动态数组结构体：ResultList 用于存储所有找到的组合，包含二维数组、各组合长度、容量和实际大小。
2. 内存管理函数：
   • createResultList：初始化结果集，预分配内存。
   • addToResult：动态扩容并复制路径数据。
   • freeResultList：递归释放所有内存。
3. 回溯函数：
   • 通过 path 数组记录当前组合，pathSize 记录当前组合长度。
   • 剪枝逻辑：若当前和超过目标，终止后续循环。
4. 输入处理：
   • 用 fgets 读取价格行，分割为整数数组。
   • 使用 qsort 对价格排序。
5. 格式化输出：遍历结果集，按题目要求拼接字符串。

示例测试

示例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ⁿ)
   • 最坏情况需遍历所有组合，剪枝大幅减少实际计算量。
2. 空间复杂度：O(k·m)
   • 结果集存储所有组合，k为组合数，m为平均组合长度。
3. 优势：
   • 手动内存管理：精准控制内存分配，适合嵌入式场景。
   • 高效剪枝：通过排序和提前终止优化性能。
4. 适用场景：
   • 需要严格内存控制的系统。
   • 中小规模数据（价格数量≤100）。

GO

问题分析

我们需要找到所有可能的价格组合，使得它们的总和等于给定的金额。每个价格可以重复使用，组合需按非降序排列以避免重复。例如，给定金额 500 和价格列表 [100,200,300,500]，组合 [100,100,300] 是有效的，而 [300,100,100] 被视为重复。

解题思路

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

代码实现

package main

import (
	"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 [][]int
	backtrack(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]]

解析：

1. 排序后价格为 [100,200,300,500]。
2. 递归过程：
   • 选择 100 5次 → [100×5]。
   • 选择 100 3次后选 200 → [100×3,200]。
   • 其他组合类似，最终输出所有非降序组合。

示例2输入：

100  
100  

输出：

解析：

• 唯一可能的组合是 [100]，直接命中目标金额。

综合分析

1. 时间复杂度：

   • 最坏情况：O(2ⁿ)，其中 n 为价格列表长度。
   • 剪枝优化后：实际运行时间远小于理论值，例如示例1中跳过所有 price > 500 的路径。

2. 空间复杂度：

   • 递归栈：O(n)，取决于价格列表长度。
   • 结果存储：O(k·m)，k 为组合数，m 为平均组合长度。

3. 优势：

   • 避免重复组合：通过排序和固定起始索引 start 实现。
   • 内存高效：Go 的切片动态扩容机制减少内存浪费。

4. 适用场景：

   • 价格数量 ≤ 100 的中小规模数据。
   • 需要精确枚举所有可能性的场景（如商品推荐系统）。

扩展

Go语言特性带来的优势：

1. 切片动态管理：无需手动处理数组扩容，简化代码。
2. 值传递与指针：通过指针传递结果切片，避免深拷贝开销。
3. 内置排序函数：sort.Ints 一行代码完成排序。

潜在改进方向：

1. 并行计算：利用 goroutine 分割搜索空间，加速大规模数据处理。
2. 内存池优化：预分配结果切片内存，减少动态扩容次数。
3. 字典树剪枝：对价格列表构建前缀树，进一步优化剪枝逻辑。

更多内容：

https://www.kdocs.cn/l/cvk0eoGYucWA

本文发表于【纪元A梦】，关注我，获取更多实用教程/资源！