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 tổ hợp có thể của k số từ 1 ... n. Ví dụ, nếu n = 4 và k = 2, tổ hợp sẽ là [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]].

Để giải quyết, chúng ta làm theo các bước sau:

• Sử dụng hàm đệ quy để giải quyết. Hàm solve() nhận n, k, mảng tạm temp và start. start ban đầu là 1. Hàm hoạt động như sau:
• Nếu kích thước mảng temp = k, chèn temp vào mảng kết quả res, và trả về.
• Với i từ start đến n:
  • Chèn i vào temp.
  • Gọi solve(n, k, temp, i + 1).
  • Loại bỏ một phần tử từ cuối temp.
• Gọi hàm solve(n, k, []).
• Trả về res.

Ví dụ

Xem triển khai sau để hiểu rõ hơn:

#include 
using namespace std;

void print_vector(vector> 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> res;
    void solve(int n, int k, vector 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> combine(int n, int k) {
        res.clear();
        vector temp;
        solve(n, k, temp);
        return res;
    }
};

int 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]]