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(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()

代碼詳細解析

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(n2)

   • 遞歸調用棧深度為 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(n2)

   • 遞歸棧深度為 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));  // 路徑最大長度設為100backtrack(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 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]]

解析：

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夢】，關注我，獲取更多實用教程/資源！