问题要求：给定一个候选数集 (candidates) 和一个目标数 (target)，找出 candidates 中所有可以使数字和为 target 的组合。
关键约束：
1. candidates 中的每个数字在每个组合中只能使用一次。
2. 解集不能包含重复的组合。
一句话就是：有重复的元素怎么得到不重复的集合
比如{1，1，1， 2}，target = 3， 问题的难点在于，最终的集合是{1， 2}，{1， 1， 1}而在以往的算法答案是{1， 2}， {1， 2}，{1， 2}为什么有三个{1， 2}，是因为有三个{1， 1， 1}， 因此难点在于怎么去重。
分析
首先我们已知回溯算法可以抽象为一颗树，分为横向和纵向，横向表示同一层的元素，比如{1， 2}， {1， 2}，{1， 2}，这是因为三个1都在第一层，分别选择了三次，纵向表示同一树枝的元素，比如{1， 1， 1}表示三个1分别在三层，他们在同一个集合，三次递归选中了1。
通过以上的分析可知，我们想要得到不重复的集合就是要在去重同一层重复的元素。
思路
首先肯定是要对元素进行排序，一方面是为了剪枝，一方面方便处理重复的元素。
去重逻辑 (关键)
当满足以下三个条件时，跳过当前元素以避免重复组合：
1. i > 0：确保 i-1 索引有效。
2. candidates[i] == candidates[i - 1]：当前元素与前一个元素相同。
3. used[i - 1] == false：前一个相同的元素在搜索中没有被使用，这表明二者是同一层的元素，如果used[i - 1] == true，表明二者是同一个树枝上的元素，所以这个条件十分重要，用来确定是同一层，还是同一树枝。
这表示我们已经处理过以 candidates[i-1] 开头的组合，现在为了避免重复，需要跳过以 candidates[i] 开头的相同组合。
if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) { continue; }代码
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; // LeetCode 问题：组合总和 II // 问题要求：给定一个候选数集 (candidates) 和一个目标数 (target)，找出 candidates 中所有可以使数字和为 target 的组合。 // 关键约束： // 1. candidates 中的每个数字在每个组合中只能使用一次。 // 2. 解集不能包含重复的组合。 class Solution { private: vector<int> path; // 存储当前正在构建的组合路径 vector<vector<int>> result; // 存储所有符合条件的最终组合 /** * @brief 核心回溯函数 * @param candidates 候选数组 * @param targetSum 目标和 * @param sum 当前路径的和 * @param startIndex 搜索的起始索引，用于防止元素重复使用 * @param used 标记数组，用于在处理重复数时去重 */ void backtracking(const vector<int>& candidates, int targetSum, int sum, int startIndex, vector<bool>& used) { // 终止条件：如果当前和等于目标值，说明找到了一个有效组合 if (sum == targetSum) { result.push_back(path); // 将当前路径添加到结果集中 return; } // 遍历候选数组 // 剪枝优化：i < candidates.size() && sum + candidates[i] <= targetSum // 如果当前元素加上当前和已经超过了目标值，那么后续更大的元素也必然超过，因此可以提前终止循环。 for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= targetSum; i++) { // 去重逻辑 (关键) // 当满足以下三个条件时，跳过当前元素以避免重复组合： // 1. i > 0：确保 i-1 索引有效。 // 2. candidates[i] == candidates[i - 1]：当前元素与前一个元素相同。 // 3. used[i - 1] == false：前一个相同的元素在搜索中没有被使用，这表明二者是同一层的元素，如果used[i - 1] == true，表明二者是同一个树枝上的元素 // 这表示我们已经处理过以 candidates[i-1] 开头的组合，现在为了避免重复， // 需要跳过以 candidates[i] 开头的相同组合。 if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) { continue; } // --- 做出选择 --- path.push_back(candidates[i]); // 将当前元素加入路径 used[i] = true; // 标记当前元素已使用 sum += candidates[i]; // 更新当前和 // --- 递归进入下一层 --- // 递归调用 backtracking，从下一个索引 i + 1 开始搜索，确保每个数字只用一次。 backtracking(candidates, targetSum, sum, i + 1, used); // --- 撤销选择 (回溯) --- sum -= candidates[i]; // 恢复当前和 used[i] = false; // 取消标记 path.pop_back(); // 将当前元素移出路径，为同层其他选择让路 } } public: /** * @brief 主函数，用于寻找所有和为 target 的组合 * @param candidates 候选数组 * @param target 目标和 * @return 返回所有符合条件的组合 */ vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { path.clear(); // 清空上一次的路径 result.clear(); // 清空上一次的结果 // 初始化 used 数组，大小与 candidates 相同，全部置为 false (未使用) vector<bool> used(candidates.size(), false); // 排序是去重逻辑的前提。排序后，所有相同的元素都会相邻排列。 sort(candidates.begin(), candidates.end()); // 从索引 0 开始进行回溯搜索 backtracking(candidates, target, 0, 0, used); return result; // 返回最终结果 } }; // --- 主测试函数 --- int main() { Solution S; // 创建 Solution 类的实例 // 测试用例：一个包含重复数字的数组 vector<int> candidates = {10, 1, 2, 7, 6, 1, 5, 2, 2, 2}; int target = 8; // 调用函数获取所有符合条件的组合 vector<vector<int>> res = S.combinationSum2(candidates, target); // --- 输出结果 --- cout << "所有和为 " << target << " 的组合：" << endl; for (auto& row : res) { // 遍历每一个组合 (row) for (auto& col : row) { // 遍历组合中的每一个数字 (col) cout << col << " "; } cout << endl; // 每个组合输出后换行 } return 0; // 程序正常退出 }
