在两个半部中所有长度相等的n的所有可能二进制数？
在这里，我们将看到所有可能的n位二进制数（n由用户给出），其中每半的总和是相同的。例如，如果数字为10001，则10和01相同，因为它们的总和相同，并且分别位于不同的一半。在这里，我们将生成该类型的所有数字。
算法
genAllBinEqualSumHalf（n，左，右，diff）
左和右最初是空的，diff保持左和右之间的差异
Begin
if n is 0, then
if diff is 0, then
print left + right
end if
return
end if
if n is 1, then
if diff is 0, then
print left + 0 + right
print left + 1 + right
end if
return
end if
if 2* |diff| <= n, then
if left is not blank, then
genAllBinEqualSumHalf(n-2, left + 0, right + 0, diff)
genAllBinEqualSumHalf(n-2, left + 0, right + 1, diff-1)
end if
genAllBinEqualSumHalf(n-2, left + 1, right + 0, diff + 1)
genAllBinEqualSumHalf(n-2, left + 1, right + 1, diff)
end if
End示例
#include <bits/stdc++.h>
using namespace std;
//左右字符串将被填充，di将保留左右之间的差异
void genAllBinEqualSumHalf(int n, string left="", string right="", int di=0) {
if (n == 0) { //when the n is 0
if (di == 0) //if diff is 0, then concatenate left and right
cout << left + right << " ";
return;
}
if (n == 1) {//if 1 bit number is their
if (di == 0) { //when difference is 0, generate two numbers one with 0 after left, another with 1 after left, then add right
cout << left + "0" + right << " ";
cout << left + "1" + right << " ";
}
return;
}
if ((2 * abs(di) <= n)) {
if (left != ""){ //numbers will not start with 0
genAllBinEqualSumHalf(n-2, left+"0", right+"0", di);
//在左右后加0-
genAllBinEqualSumHalf(n-2, left+"0", right+"1", di-1);
//在左后加0，在右后加1，所以相差少1-
}
genAllBinEqualSumHalf(n-2, left+"1", right+"0", di+1); //add 1 after left, and 0 after right, so difference is 1 greater
genAllBinEqualSumHalf(n-2, left+"1", right+"1", di); //add 1 after left and right
}
}
main() {
int n = 5;
genAllBinEqualSumHalf(n);
}输出结果
100001 100010 101011 110011 100100 101101 101110 110101 110110 111111