194.回溯算法：组合总和||（力扣）

代码解决

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：
       • 超过目标值，回溯。