c++在数组中查找不重复组合
时间: 2025-04-04 22:06:55 浏览: 32
### C++ 中数组不重复组合算法的实现
在处理数组中的不重复组合问题时,可以采用回溯法来解决。这种方法通过递归的方式枚举所有可能的组合,并利用条件判断排除掉重复的情况。
以下是基于回溯方法的一个具体实现:
#### 方法描述
为了生成给定数组 `arr` 的所有长度为 `k` 的不重复组合,可以通过以下方式完成:
- 首先对输入数组进行排序,以便更容易跳过重复项。
- 使用一个辅助函数来进行递归调用,在每次递归过程中记录当前路径并更新剩余可选元素范围。
- 如果发现相邻两个数相同,则跳过后续相同的分支以避免产生重复的结果。
下面是完整的代码示例[^1]:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void backtrack(vector<vector<int>>& res, vector<int>& current, const vector<int>& nums, int start, int k) {
if (current.size() == k) { // 当前组合达到指定大小
res.push_back(current);
return;
}
for (int i = start; i < nums.size(); ++i) {
if (i > start && nums[i] == nums[i - 1]) continue; // 跳过重复元素
current.push_back(nums[i]); // 做选择
backtrack(res, current, nums, i + 1, k); // 进入下一层决策树
current.pop_back(); // 撤销选择
}
}
vector<vector<int>> combineUnique(const vector<int>& nums, int k) {
sort(nums.begin(), nums.end()); // 排序便于去重
vector<vector<int>> result;
vector<int> current;
backtrack(result, current, nums, 0, k);
return result;
}
int main() {
vector<int> arr = {1, 2, 2};
int k = 2;
vector<vector<int>> combinations = combineUnique(arr, k);
cout << "Combinations of size " << k << ":" << endl;
for (const auto& comb : combinations) {
for (int num : comb) {
cout << num << " ";
}
cout << endl;
}
return 0;
}
```
上述程序实现了从含有重复元素的数组中提取唯一组合的功能。它会自动过滤掉那些由于重复而导致的冗余结果[^2]。
#### 关键点解析
- **排序操作**:通过对原始数据集预先排序,能够方便地识别连续相等数值的位置从而简化逻辑控制流程。
- **剪枝策略**:当检测到某次迭代即将访问已经考察过的节点或者其子结构时立即停止进一步探索该方向上的可能性。
阅读全文
相关推荐


















