Kết hợp trong C ++

Giả sử chúng ta có hai số nguyên n và k. Chúng ta phải tìm tất cả các kết hợp có thể có của k số trong số 1 ... n. Vì vậy, nếu n =4 và k =2, thì các kết hợp sẽ là [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4 ]]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Chúng tôi sẽ sử dụng hàm đệ quy để giải quyết vấn đề này. hàm giải quyết () đang lấy n, k, mảng tạm thời và bắt đầu. Khởi đầu ban đầu là 1. Điều này sẽ hoạt động như thế nào
• nếu kích thước của mảng tạm thời =k, sau đó chèn tạm thời vào mảng res và trả về
• for i:=start to n,
  • chèn tôi vào tạm thời
  • giải quyết (n, k, tạm thời, i + 1)
  • xóa một phần tử khỏi phần cuối tạm thời
• gọi hàm giải quyết như giải quyết (n, k, [])
• trả lại res

Ví dụ

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

#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 n, int k, vector <int> temp, int start = 1){
      if(temp.size() == k){
         res.push_back(temp);
         return;
      }
      for(int i = start; i <= n; i++){
         temp.push_back(i);
         solve(n, k, temp, i + 1);
         temp.pop_back();
      }
   }
   vector<vector<int> > combine(int n, int k) {
      res.clear();
      vector <int> temp;
      solve(n ,k, temp);
      return res;
   }
};
main(){
   Solution ob;
   print_vector(ob.combine(5,3));
}

Đầu vào

5
3

Đầu ra

[[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5]]