Today's Little Program prints all bit strings of length `n`
subject to the requirement that the string have exactly `k`
1-bits.
For example, all bit strings of length 4 with 2 bits set are
0011, 0101, 0110, 1001, 1010, and 1100.
Let's write
BitString(`n`, `k`) to mean all the bit strings
of length `n` with exactly `k` bits set.

Let's look at the last bit of a typical member of
BitString(`n`, `k`).
If it is a zero, then removing it leaves a string one bit shorter
but with the same number of bits set.
Conversely every BitString(`n` − 1, `k`) string
can be extended to a BitString(`n`, `k`) string
by adding a zero to the end.

If the last bit is a one, then
removing it leaves a bit string of
length `n` − 1 with exactly `k` − 1 bits set,
and conversely every bit string of length `n` − 1 with
exactly `k` − 1 bits set can be extended to a bit string of
length `n` with exactly `k` bits set by adding a one to the end.

Therefore, our algorithm goes like this:

- Handle base cases.
- Otherwise,
- Recursively call
BitString(
`n`− 1,`k`) and add a 0 to the end. - Recursively call
BitString(
`n`− 1,`k`− 1) and add a 1 to the end.

- Recursively call
BitString(

This algorithm may look awfully familiar. The overall recursive structure is the same as enumerating subsets with binomial coefficients; we just decorate the results differently.

That's because this problem is the same as the problem of enumerating subsets. You can think of the set bits as selecting which elements get put into the subset.

It's not surprising, therefore, that the resulting code is identical except for how we report the results. (Instead of generating arrays, we generate strings.)

function repeatString(s, n) { return new Array(n+1).join(s); } function BitString(n, k, f) { if (k == 0) { f(repeatString("0", n)); return; } if (n == 0) { return; } BitString(n-1, k, function(s) { f(s + "0"); }); BitString(n-1, k-1, function(s) { f(s + "1"); }); }

If `k`

is zero, then that means we are looking
for strings of length `n`

that contain no bits set at all.
There is exactly one of those, namely the string consisting
of `n`

zeroes.

If `k`

is nonzero but `n`

is zero,
then that means we want strings of length zero with some bits set.
That's not possible, so we return without generating anything.

Finally, we handle the recursive case by generating the shorter strings and tacking on the appropriate digits.

Since this is the same algorithm as subset generation, we should be able to write one in terms of the other:

function BitString(n, k, f) { Subsets(n, k, function(s) { var str = ""; for (var i = 1; i <= n; i++) { str += s.indexOf(i) >= 0 ? "1" : "0"; } f(str); }); }