In Tất Cả Số Nhỏ Hơn N Với Tối Đa 2 Chữ Số Riêng Biệt Trong C++

Trong bài toán này, chúng ta được cho một số nguyên N và phải in tất cả số nhỏ hơn N với tối đa 2 chữ số riêng biệt, tức là tối đa 2 chữ số khác nhau tạo thành số.

Ví dụ để hiểu vấn đề:

Đầu vào: N = 17 → Đầu ra: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Để giải quyết, ta sinh tất cả số chỉ có hai chữ số duy nhất. Quá trình sinh bắt đầu từ 0 và dừng khi số ≥ N. Với hai chữ số i, j được chọn, đệ quy sinh số bằng num*10+i và num*10+j. Có thể sinh trùng lặp, dùng set để lưu trữ và loại bỏ.

Ví Dụ

Chương trình triển khai giải pháp:

#include <bits/stdc++.h>
using namespace std;

set<int> numbers;

void generateNumbers(int n, int num, int i, int j) {
    if (num > 0 && num < n)
        numbers.insert(num);
    if (num >= n)
        return;
    if (num * 10 + i > num)
        generateNumbers(n, num * 10 + i, i, j);
    generateNumbers(n, num * 10 + j, i, j);
}

void printUniqueBitNumber(int n) {
    for (int i = 0; i <= 9; i++)
        for (int j = i + 1; j <= 9; j++)
            generateNumbers(n, 0, i, j);
    cout << "Các số được sinh là: ";
    while (!numbers.empty()) {
        cout << *numbers.begin() << " ";
        numbers.erase(numbers.begin());
    }
}

int main() {
    int n = 17;
    printUniqueBitNumber(n);
    return 0;
}

Đầu Ra

Các số được sinh là: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16