C++ 中的组合总和 II
c++server side programmingprogramming更新于 2024/9/1 2:49:00
假设我们有一组候选数字(所有元素都是唯一的)和一个目标数字。我们必须在候选数字中找到所有唯一组合，使候选数字的总和等于给定的目标。同一个数字不会从候选数字中被选中超过一次。因此，如果元素为 [2,3,6,7,8] 且目标值为 8，则可能的输出将是 [[2,6],[8]]
让我们看看步骤 −
- 我们将以递归方式解决这个问题。递归函数名为solve()。它需要 index、数组 a、整数 b 和另一个数组 temp。解决方法将像下面这样工作 −
- 定义空数组 res
- 如果 b = 0，则将 temp 插入 res，并返回
- 如果 index = a 的大小，则返回
- 如果 b < 0，则返回
- 对数组 a 进行排序
- for i in range index to size of a – 1
- if i > index and a[i] = a[i – 1]，然后继续
- 将 a[i] 插入到 temp 中
- solve(i + 1, a, b – a[i], temp)
- 从 temp 中删除最后一个元素
- 通过传递 index = 0、数组 a、目标 b 和另一个数组 temp 来调用solve() 方法
- return res
让我们看看下面的实现以便更好地理解 −
示例
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<int> > v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
class Solution {
public:
vector < vector <int> > res;
void solve(int idx, vector <int> &a, int b, vector <int> temp){
if(b == 0){
res.push_back(temp);
return;
}
if(idx == a.size())return;
if(b < 0)return;
sort(a.begin(), a.end());
for(int i = idx; i < a.size(); i++){
if(i > idx && a[i] == a[i-1])continue;
temp.push_back(a[i]);
solve(i + 1, a, b - a[i], temp);
temp.pop_back();
}
}
vector<vector<int> > combinationSum2(vector<int> &a, int b) {
res.clear();
vector <int> temp;
solve(0, a, b, temp);
return res;
}
};
main(){
Solution ob;
vector<int> v = {2,3,6,7,8};
print_vector(ob.combinationSum2(v, 10)) ;
}
输入
[2,3,6,7,8] 8
输出
[[2, 8, ],[3, 7, ],]
