Tổng kết hợp II trong C ++

Giả sử chúng ta có một tập hợp các số ứng viên (tất cả các phần tử là duy nhất) và một số mục tiêu. Chúng tôi phải tìm tất cả các kết hợp duy nhất trong các ứng cử viên mà số ứng viên tổng hợp thành mục tiêu đã cho. Số lượng giống nhau sẽ không được chọn từ các ứng viên nhiều hơn một lần. Vì vậy, nếu các phần tử là [2,3,6,7,8] và giá trị đích là 8, thì đầu ra có thể sẽ là [[2,6], [8]]

Hãy để chúng tôi xem các bước -

• Chúng tôi sẽ giải quyết vấn đề này theo cách đệ quy. Hàm đệ quy được đặt tên là giải quyết (). Điều này nhận chỉ số, một mảng a, số nguyên b và một mảng khác tạm thời. Phương thức giải sẽ hoạt động như bên dưới -
• Xác định res mảng trống
• nếu b =0, sau đó chèn tạm thời vào res và trả về
• if index =size of a, then return
• nếu b <0, thì trả về
• sắp xếp mảng a
• for i in range index to size a - 1
  • if i> index and a [i] =a [i - 1], then continue
  • chèn [i] vào tạm thời
  • giải quyết (i + 1, a, b - a [i], tạm thời)
  • xóa phần tử cuối cùng khỏi tạm thời
• gọi phương thức giải quyết () bằng cách truyền chỉ số =0, mảng a và đích b và một mảng tạm thời khác
• trả lại res

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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)) ;
}

Đầu vào

[2,3,6,7,8]
8

Đầu ra

[[2, 8, ],[3, 7, ],]