Sinh số nhị phân n bit tổng 2 nửa bằng nhau trong C++

Sinh tất cả số nhị phân n bit (n chẵn) mà tổng bit nửa đầu = tổng bit nửa sau.

Ví dụ n=4

1001 (1+0=0+1), 1010, 0101, 0110, 1100, 0011...

Thuật toán đệ quy

Xây dựng từ 2 đầu về giữa, theo dõi chênh lệch diff. Chỉ tiếp tục nếu 2|diff| ≤ số bit còn lại.

Chương trình

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

void gen(int n, string left="", string right="", int diff=0) {
    if (n == 0) {
        if (diff == 0) cout << left + right << " ";
        return;
    }
    if (n == 1) {
        if (diff == 0) { cout << left + "0" + right << " "; cout << left + "1" + right << " "; }
        return;
    }
    if (2 * abs(diff) <= n) {
        if (!left.empty()) {
            gen(n-2, left+"0", right+"0", diff);
            gen(n-2, left+"0", right+"1", diff-1);
        }
        gen(n-2, left+"1", right+"0", diff+1);
        gen(n-2, left+"1", right+"1", diff);
    }
}

int main() {
    gen(6); // n phải chẵn
    return 0;
}

Kết quả (n=6)

100001 100010 101011 110011 100100 101101 101110 110101 110110 111111