"组合总和 II 是一个经典的算法问题，主要涉及回溯搜索和数组排序。此问题的目标是找到一个数组 candidates 中的所有不重复组合，这些组合的元素相加等于给定的目标数 target。"
## 知识点详解
### 1. 回溯搜索 (Backtracking)
回溯搜索是一种在解决问题时避免走入死胡同的方法，它通过尝试所有可能的分支来寻找解决方案，当发现当前分支无法得到解时，会回退到上一步，尝试其他路径。在组合总和 II 的问题中，回溯搜索是核心算法，用于遍历所有可能的组合。
### 2. 数组排序 (Array Sorting)
在解决这个问题前，先对数组 candidates 进行排序是非常重要的。这有助于在回溯过程中避免重复的组合。例如，如果未排序的数组中有两个相同的元素，不进行排序可能会导致重复的组合出现。
### 3. 自定义数据结构 (Custom Data Structure)
在提供的参考答案中，`freq` 是一个 `vector<pair<int, int>>`，用于存储数组 candidates 中每个元素出现的频率。`freq[pos].first` 存储元素值，`freq[pos].second` 存储该元素出现的次数。这样的数据结构有利于在回溯过程中快速统计和操作元素。
### 4. 递归函数 (Recursive Function)
`dfs(pos, rest)` 是一个递归函数，用于深度优先搜索所有可能的组合。`pos` 表示当前处理 candidates 的位置，`rest` 表示还需要多少数值才能达到目标 target。
### 5. 最小值判断 (Minimum Value Check)
在递归函数中，`if(pos==freq.size()||rest<freq[pos].first){ return; }` 这一行代码检查了当前位置是否越界或者剩余值不足以从当前位置的元素中选择，如果满足条件则返回，避免无效的搜索。
### 6. 重复元素处理 (Duplicate Element Handling)
对于重复的元素，参考答案使用了一个技巧：如果当前元素与前一个元素相同，且前一个元素的计数还没用完（即 `freq.back().second > 0`），那么可以跳过这个元素，防止重复组合的产生。
### 7. 分支剪枝 (Branch Pruning)
在回溯过程中，`for(int i=1; i<=most; ++i)` 循环用于尝试从当前位置选取 i 个元素，`most` 计算为 `min(rest/freq[pos].first, freq[pos].second)`，确保选取的元素不超过目标值且不超出当前元素的可用次数。这一步骤实现了剪枝，减少了不必要的搜索。
### 8. 结果存储 (Result Storage)
最后，将成功满足条件的组合存储在 `vector<vector<int>> ans` 中，并在主函数中返回。
总结，组合总和 II 的解决方案主要利用了回溯搜索，结合数组排序和数据结构优化，高效地找出所有符合条件的组合，同时避免了结果的重复。
我的内容管理
展开
