C ++中的组合和II

假设我们有一组候选编号（所有元素都是唯一的）和一个目标编号。我们必须在候选者中找到所有唯一组合，其中候选者数字之和等于给定目标。将从候选人中多次选择相同的号码。因此，如果元素为[2,3,6,7,8]并且目标值为8，则可能的输出将为[[2,6]，[8]]

让我们看看步骤-

• 我们将以递归方式解决此问题。递归函数名为solve()。这需要索引，数组a，整数b和另一个数组temp。解决方法将如下工作-

• 定义空数组资源

• 如果b = 0，则将temp插入res，然后返回

• 如果index = a的大小，则返回

• 如果b <0，则返回

• 对数组进行排序

• 因为我的范围指数是a – 1

• 如果i>索引并且a [i] = a [i – 1]，则继续

• 在温度中插入a [i]

• resolve（i + 1，a，b – a [i]，temp）

• 删除temp中的最后一个元素

• solve()通过传递index = 0，数组a和目标b以及另一个数组temp来调用该方法

• 返回资源

让我们看下面的实现以更好地理解-

示例

#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, ],]