เลขฐานสองความยาว n ที่ผลรวมครึ่งซ้าย=ครึ่งขวา ในภาษา C

สร้างเลขฐานสอง n บิต (n คู่) ที่ผลรวมบิตครึ่งแรก = ผลรวมบิตครึ่งหลัง

อัลกอริทึม Recursive

สร้างทีละคู่บิต (ซ้าย, ขวา) ติดตามความต่าง diff = sum_left - sum_right

Pruning: ถ้า 2×|diff| > เหลือบิต → หยุด

โค้ดตัวอย่าง (C++)

#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 << " " << 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); return 0; }

ผลลัพธ์ n=6

100001 100010 101011 110011 100100 101101 101110 110101 110110 111111