代碼解決

class Solution {
public:vector<int> res; // 當前組合的臨時存儲vector<vector<int>> result; // 存儲所有符合條件的組合// 回溯函數void backtracing(vector<int>& candidates, int target, int flag, int index, vector<bool>& used) {// 如果當前組合的和超過了目標值，則返回if (flag > target) return;// 如果當前組合的和等于目標值，則將當前組合加入結果集if (flag == target) {result.push_back(res);return;}// 遍歷候選數組for (int i = index; i < candidates.size() && flag + candidates[i] <= target; i++) {// 如果當前元素和上一個元素相同且上一個元素沒有被使用，跳過以避免重復組合if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) {continue;}// 更新當前組合和flag += candidates[i];// 將當前元素加入當前組合res.push_back(candidates[i]);// 標記當前元素已使用used[i] = true;// 遞歸調用回溯函數，當前索引右移一位backtracing(candidates, target, flag, i + 1, used);// 回溯，移除當前元素used[i] = false;res.pop_back();flag -= candidates[i];}}// 主函數vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {vector<bool> used(candidates.size(), false); // 標記數組，用于記錄元素是否已被使用sort(candidates.begin(), candidates.end()); // 排序輸入數組backtracing(candidates, target, 0, 0, used); // 初始調用回溯函數return result; // 返回所有符合條件的組合}
};

測試用例

輸入

vector<int> candidates = {10, 1, 2, 7, 6, 1, 5}; int target = 8;

輸出

[ [1, 1, 6], [1, 2, 5], [1, 7], [2, 6] ]

過程描述

1. 初始狀態：

   • candidates = {1, 1, 2, 5, 6, 7, 10}（排序后）
   • target = 8
   • res = []（當前組合為空）
   • result = []（所有符合條件的組合為空）
   • used = {false, false, false, false, false, false, false}（所有元素未使用）

2. 遞歸回溯：

   • 從第一個元素 1 開始：
     • flag = 1，res = [1]，繼續遞歸。
     • 再次選擇 1：
       • flag = 2，res = [1, 1]，繼續遞歸。
       • 選擇 6：
         • flag = 8，res = [1, 1, 6]，符合目標值，將組合加入 result，回溯，移除 6。
       • 選擇 2：
         • flag = 4，res = [1, 1, 2]，繼續遞歸。
         • 選擇 5：
           • 超過目標值，回溯，移除 2。
       • 選擇 5，6，7，10：
         • 超過目標值，回溯。
     • 選擇 2：
       • flag = 3，res = [1, 2]，繼續遞歸。
       • 選擇 5：
         • flag = 8，res = [1, 2, 5]，符合目標值，將組合加入 result，回溯，移除 5。
       • 選擇 6，7，10：
         • 超過目標值，回溯。
   • 選擇 6：
     • flag = 7，res = [1, 6]，繼續遞歸。
     • 選擇 7，10：
       • 超過目標值，回溯。
   • 選擇 7：
     • flag = 8，res = [1, 7]，符合目標值，將組合加入 result，回溯，移除 7。
   • 選擇 10：
     • 超過目標值，回溯。
   • 選擇 2：
     • flag = 2，res = [2]，繼續遞歸。
     • 選擇 6：
       • flag = 8，res = [2, 6]，符合目標值，將組合加入 result，回溯，移除 6。
     • 選擇 7，10：
       • 超過目標值，回溯。
   • 選擇 5：
     • flag = 5，res = [5]，繼續遞歸。
     • 選擇 6，7，10：
       • 超過目標值，回溯。