Editorial for binary: Liệt kê chuỗi nhị phân

Hiểu bài toán

Bài toán yêu cầu in ra tất cả các chuỗi nhị phân có độ dài n theo thứ tự từ điển. Chuỗi nhị phân là chuỗi chỉ bao gồm các ký tự '0' và '1'. Thứ tự từ điển tăng dần tương ứng với việc coi chuỗi nhị phân như một số ở cơ số 2 với '0' là bit 0 và '1' là bit 1, và liệt kê từ số 0 đến 2^n - 1.

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

Cách Duyệt qua các số nguyên

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    int total = 1 << n; // 2^n
    for (int i = 0; i < total; i++) {
        for (int j = n - 1; j >= 0; j--) {
            if ((i >> j) & 1) printf("1");
            else printf("0");
        }
        printf("\n");
    }
    return 0;
}

• Time Complexity: O(n * 2^n)
• Space Complexity: O(1)

Phương pháp này sử dụng một vòng lặp chính chạy từ 0 đến 2^n - 1. Với mỗi số nguyên i, ta duyệt qua từng bit của nó từ bit cao nhất (vị trí n-1) xuống bit thấp nhất (vị trí 0). Sử dụng phép dịch bit (shift) và phép AND, ta kiểm tra giá trị của bit tại mỗi vị trí và in ra '1' hoặc '0' tương ứng. Cách này rất trực quan và mã nguồn ngắn gọn.

Cách Sử dụng mảng động (Backtracking/Increment)

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    int a[n];
    // Khởi tạo chuỗi đầu tiên là toàn 0
    for(int i = 0; i < n; i++) {
        a[i] = 0;
        printf("0");
    }
    printf("\n");

    while(1) {
        int found = 0;
        // Tìm vị trí bit 0 đầu tiên từ phải sang trái
        for(int i = n - 1; i >= 0; i--) {
            if(a[i] == 0) {
                a[i] = 1; // Đổi 0 thành 1
                // Đặt tất các bit bên phải thành 0
                for(int j = i + 1; j < n; j++) {
                    a[j] = 0;
                }
                found = 1;
                break;
            }
        }
        if(!found) break; // Không tìm thấy 0 nào -> đã là chuỗi cuối (toàn 1)

        // In chuỗi hiện tại
        for(int i = 0; i < n; i++) printf("%d", a[i]);
        printf("\n");
    }
    return 0;
}

• Time Complexity: O(n * 2^n)
• Space Complexity: O(n)

Phương pháp này mô phỏng quá trình đếm số nhị phân. Nó bắt đầu với chuỗi toàn '0'. Ở mỗi bước, nó tìm bit '0' đầu tiên từ phải sang trái, đổi bit này thành '1', và đặt tất cả các bit nằm sau nó (bên phải) thành '0'. Quá trình này lặp lại cho đến khi không thể tìm thấy bit '0' nào nữa (tức là chuỗi toàn '1'). Đây là cách tư duy 'tự nhiên' để tạo ra các chuỗi theo thứ tự.

Cách Quay lui (Recursive Backtracking)

#include <stdio.h>
#include <string.h>

char str[25];

void generate(int n, int pos) {
    if (pos == n) {
        printf("%s\n", str);
        return;
    }
    str[pos] = '0';
    generate(n, pos + 1);
    str[pos] = '1';
    generate(n, pos + 1);
}

int main() {
    int n;
    scanf("%d", &n);
    str[n] = '\0'; // Kết thúc chuỗi
    generate(n, 0);
    return 0;
}

• Time Complexity: O(n * 2^n)
• Space Complexity: O(n) (stack depth)

Sử dụng kỹ thuật quay lui (recursion). Hàm generate nhận vào độ dài n và vị trí hiện tại pos. Nếu pos bằng n, tức là đã tạo xong một chuỗi, ta in ra. Ngược lại, ta thử gán ký tự '0' vào vị trí pos, gọi đệ quy cho vị trí tiếp theo, sau đó thử gán ký tự '1' và gọi đệ quy. Vì ta gọi đệ quy cho '0' trước rồi mới đến '1', thứ tự từ điển được đảm bảo.

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

Bài học kinh nghiệm

• Bài toán này có thể được coi là bài toán liệt kê các số từ 0 đến 2^n - 1 ở hệ nhị phân.
• Thứ tự từ điển tăng dần tương đương với thứ tự số học tăng dần.
• Có thể giải quyết bằng cách duyệt tuần tự các số (iteration) hoặc bằng cách sinh chuỗi động (quay lui hoặc mô phỏng phép cộng)

Lỗi thường gặp

• Lỗi in sai thứ tự do duyệt bit sai chiều (ví dụ: in bit thấp nhất trước thay vì bit cao nhất). Cần duyệt từ n-1 về 0.
• Sử dụng sai toán tử dịch bit (dịch phải arithmetic shift >> vs dịch trái <<).
• Đối với phương pháp mảng động, việc không reset các bit bên phải sau khi đổi một bit từ 0 thành 1 sẽ dẫn đến thứ tự sai.