Hiểu bài toán

Bài toán yêu cầu sinh và in ra tất cả các cách chọn k số nguyên dương phân biệt từ 1 đến n sao cho chúng tăng dần, cùng với tổng số cách chọn đó. Nói cách khác, bài toán yêu cầu sinh tất cả các tổ hợp k phần tử của tập hợp {1, 2, ..., n}. Sau khi in ra tất cả các tổ hợp (định dạng (a1,a2,...,ak)), cần in ra số lượng tổ hợp đã sinh ra.

Các cách tiếp cận

Cách Quay lui (Backtracking)

#include <iostream>
using namespace std;
int x[100005];
long long d = 0;
void ql(int start, int n, int cauhinh, int k) {
    if (cauhinh == k) {
        cout << "(";
        for (int i = 0; i < k - 1; i++) {
            cout << x[i] << ",";
        }
        cout << x[k - 1] << ")" << endl;
        d++;
        return;
    }
    for (int i = start; i <= n; i++) {
        x[cauhinh] = i;
        ql(i + 1, n, cauhinh + 1, k);
    }
}
int main() {
    freopen("silicon.inp", "r", stdin);
    freopen("silicon.out", "w", stdout);
    int n, k;
    cin >> n >> k;
    ql(1, n, 0, k);
    cout << d;
    return 0;
}

• Time Complexity: O(C(n, k) * k)
• Space Complexity: O(k)

Đây là cách tiếp cận trực quan nhất. Hàm ql(start, n, cauhinh, k) sẽ cố gắng chọn phần tử tiếp theo cho vị trí cauhinh.

• start là số nhỏ nhất có thể chọn để đảm bảo tính tăng dần.
• Khi cauhinh == k, một tổ hợp hợp lệ đã được hình thành và được in ra.
• Vòng lặp for duyệt qua các số có thể chọn từ start đến n.
• Độ phức tạp thời gian là O(C(n, k)) vì chúng ta phải duyệt qua tất cả các tổ hợp. Mỗi tổ hợp mất O(k) để in ra.
• Độ phức tạp không gian là O(k) do độ sâu của đệ quy và mảng x lưu cấu hình.

Cách Sử dụng Queue (BFS)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    freopen("silicon.inp", "r", stdin);
    freopen("silicon.out", "w", stdout);
    int n, k;
    cin >> n >> k;
    queue<vector<int>> q;
    for (int i = 1; i <= n - k + 1; i++) {
        q.push({i});
    }
    while (q.front().size() < k) {
        vector<int> tam = q.front();
        q.pop();
        int l = tam[tam.size() - 1];
        for (int i = l + 1; i <= n; i++) {
            vector<int> c = tam;
            c.push_back(i);
            q.push(c);
        }
    }
    ll ans = q.size();
    while (!q.empty()) {
        vector<int> d = q.front();
        q.pop();
        cout << "(";
        for (int i = 0; i < k; i++) {
            if (i == k - 1) cout << d[i] << ")";
            else cout << d[i] << ",";
        }
        cout << endl;
    }
    cout << ans;
}

• Time Complexity: O(C(n, k) * k)
• Space Complexity: O(C(n, k) * k)

Cách tiếp cận này mô phỏng quá trình sinh tổ hợp bằng cách sử dụng hàng đợi (Queue) tương tự như duyệt theo chiều rộng (BFS).

• Ban đầu, hàng đợi chứa các vector có 1 phần tử từ 1 đến n-k+1.
• Trong khi độ dài các vector ở đầu hàng đợi chưa bằng k, ta lấy vector đó ra và thêm vào các số lớn hơn phần tử cuối cùng của nó để tạo ra các vector mới độ dài tăng thêm 1.
• Khi tất cả các vector trong hàng đợi có độ dài k, chúng chính là các tổ hợp cần tìm.
• Cách này sinh ra đúng C(n, k) tổ hợp, nhưng tốn nhiều bộ nhớ hơn do lưu trữ tất cả các cấu hình trung gian trong queue.

Cách Sử dụng Mảng và Vòng lặp (Iterative)

#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

void generateCombinations(int n, int k, ofstream &out) {
    vector<int> combination(k);
    for (int i = 0; i < k; ++i) {
        combination[i] = i + 1;
    }
    long long count = 0;
    while (true) {
        out << "(";
        for (int i = 0; i < k - 1; ++i) {
            out << combination[i] << ",";
        }
        out << combination[k - 1] << ")";
        out << "\n";
        count++;
        // Tìm vị trí để tăng
        int i = k - 1;
        while (i >= 0 && combination[i] == n - k + i + 1) {
            i--;
        }
        if (i < 0) break; // Đã sinh hết
        // Tăng và cập nhật các phần tử sau
        combination[i]++;
        for (int j = i + 1; j < k; ++j) {
            combination[j] = combination[j - 1] + 1;
        }
    }
    out << count << "\n";
}

int main() {
    ifstream inp("SILICON.INP");
    ofstream out("SILICON.OUT");
    int n, k;
    inp >> n >> k;
    generateCombinations(n, k, out);
    return 0;
}

• Time Complexity: O(C(n, k) * k)
• Space Complexity: O(k)

Đây là phương pháp sinh tổ hợp tối ưu nhất trong 3 phương pháp, thường được gọi là thuật toán "next combination". Nó sử dụng một mảng combination để lưu tổ hợp hiện tại.

1. Bắt đầu với tổ hợp đầu tiên: (1, 2, ..., k).
2. Tìm vị trí i từ phải sang trái mà tại đó combination[i] có thể tăng lên (tức là combination[i] < n - k + i + 1).
3. Tăng giá trị tại vị trí combination[i] lên 1.
4. Cập nhật các phần tử bên phải i để chúng thành một dãy tăng dần liên tục bắt đầu từ combination[i] + 1.
5. Lặp lại cho đến khi không tìm được vị trí nào để tăng. Phương pháp này rất hiệu quả về mặt không gian (chỉ cần O(k) bộ nhớ) và tinh tế trong việc xử lý.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Vấn đề là sinh các tổ hợp k phần tử của n phần tử, không phải xâu kí tự.
• Tất cả các giải pháp đều dựa trên việc đảm bảo thứ tự tăng dần để tránh lặp và liệt kê đúng.
• Giá trị C(n, k) có thể rất lớn, nhưng trong bài này chỉ yêu cầu in ra số lượng sau cùng, không cần tính toán giá trị lớn này trước.

Lỗi thường gặp

• Lưu ý định dạng in ra: (a1,a2,...,ak) theo sau là dấu phẩy giữa các số và không có dấu phẩy thừa ở cuối.
• Sử dụng biến đếm kiểu long long nếu C(n, k) có thể vượt quá 2^31 - 1.
• Đối với giải pháp dùng Queue, cần chú ý đến giới hạn bộ nhớ nếu n và k lớn vì số lượng tổ hợp tăng rất nhanh.