LESSON 268 OF 347 · BACKTRACKING

Generate Binary Strings With K Ones in C#: Backtracking

Practice O(2^n) Read the full explanation

Given two non-negative integers N and K, return the binary strings of length N with exactly K ones

Example:

Input: N = 4, K = 2
Output: [
    "1100",
    "1010",
    "1001",
    "0110",
    "0101",
    "0011"
]

Notes: K <= N <= 20

STEP 1 OF 11

Guided

Ctrl + Enter to check

C# · BACKTRACKING

Generate Binary Strings With K Ones in C#, explained

Problem overview

The method GenerateBinaryStrings receives two non-negative integers, n and k, with k <= n <= 20. It must return every binary string of length n that contains exactly k ones, as a List<string>.

For n = 4 and k = 2 there are six such strings: 0011, 0101, 0110, 1001, 1010 and 1100. Each has four characters and exactly two of them are 1. The count is the number of ways to choose which 2 of the 4 positions hold ones, which is 6.

Approach: choose a character for each position

Building the strings position by position is a decision tree. At every position there are two choices, 0 or 1, and after n positions the string is complete. Looking at every complete string and counting its ones would work, but the search can be smarter if it tracks a budget: the number of ones it is still allowed to place.

The recursion carries three things: the prefix built so far (current), the target length (n) and the remaining budget of ones (k). Appending a 0 leaves the budget alone, and appending a 1 spends one unit of it. That gives two rules:

If the budget drops to -1, the prefix already holds more ones than allowed, so no completion can be valid. The branch ends there.
When the prefix reaches length n, it is complete. It is valid only if the budget is exactly 0; a positive leftover means the string has too few ones. Either way the recursion stops growing it.

Here is n = 2, k = 1. The empty string branches to "0" (budget 1) and "1" (budget 0). From "0" we get "00" with budget 1, which is complete but has a leftover, so it is dropped, and "01" with budget 0, which is stored. From "1" we get "10" with budget 0, which is stored, and "11" with budget -1, which is cut off. The result is "01" and "10".

Step by step

Add a field of type List<string> named solutions above GenerateBinaryStrings, so the method and the recursive helper can both reach it.
Create a fresh list on each call. solutions = new(); takes its type from the field, and it prevents results of an earlier call from leaking into this one.
Start the recursion with an empty prefix "", the length n and the full budget k.
Return solutions.
Declare Generate. It is a public void method with the parameters string current, int n and int k.
Cut off overspending. If k == -1, return.
Detect a complete string: current.Length == n.
Keep it only if the budget is spent exactly. Inside the length check, add current to solutions when k == 0.
Return from the length check in every case, so the string is never extended past n characters.
Branch on '0'. Recurse with current + '0' and the same k.
Branch on '1'. Recurse with current + '1' and k - 1.

The solution in C#

class Solution {
    public void Generate(string current, int n, int k) {
        if (k == -1) {
            return;
        }
        if (current.Length == n) {
            if (k == 0) {
                solutions.Add(current);
            }
            return;
        }
        Generate(current + '0', n, k);
        Generate(current + '1', n, k - 1);
    }

    List<string> solutions;
    public List<string> GenerateBinaryStrings(int n, int k) {
        solutions = new();
        Generate("", n, k);
        return solutions;
    }
}

The C# details worth a closer look:

Strings are immutable. current + '0' creates a new string and leaves current untouched. After the first recursive call returns, the second line can still use the original prefix, and there is no need to remove a character afterwards.
String plus char. Because current is a string, the + appends the character as text. The characters here are written with single quotes ('0', a char) and the empty prefix with double quotes ("", a string). The result is still a string.
Target-typed new(). The expression new() with no type name works when the compiler can infer the type from the assignment target. Here the field is a List<string>, so it creates one.
Length versus Count. A string reports its size through the property Length, without parentheses, while a List uses Count.
The order of the results. Since '0' is tried before '1', the strings come out in ascending order: 0011 first and 1100 last.

Complexity

Time: O(2^n * n) in the worst case. The only early exit is the overspending check, so the tree can still grow to about 2^n complete strings, and building each one by repeated concatenation copies up to n characters. A budget that has run out cuts branches that place too many ones. A branch with too few ones is only discovered at full length. For the largest input, n = 20, the tree is about a million leaves, which is still fast. A tighter check, one that stops a branch when the positions left are fewer than the ones still owed, would prune that too, but the lesson keeps the code minimal.

Space: O(n) besides the output. The recursion is at most n calls deep and each call holds one prefix. The result list holds C(n, k) strings of length n each, which is the answer itself.

Edge cases and common mistakes

k = 0. The only string is all zeros, for example "000" for n = 3.
k = n. The only string is all ones, for example "111" for n = 3.
k > n. No string can hold that many ones, so the method returns an empty list. The lesson's limits exclude this case, but the code handles it.
n = 0. With k = 0 the result is a list with one empty string. The prefix is already complete at the start.
Dropping the length check's return. Without it the recursion keeps appending characters to a full-length string and never ends.
Accepting leftover budget. Adding every full-length string would include strings with fewer than k ones. The test k == 0 is what makes the count exact.
Passing k unchanged on a one. Then the budget never shrinks and the overspending check never triggers.
Not resetting solutions. A second call would return the results of the first call as well.

Testing

n = 4, k = 2 gives 0011, 0101, 0110, 1001, 1010, 1100.
n = 3, k = 0 gives 000.
n = 3, k = 3 gives 111.
n = 20, k = 10 gives 184,756 strings.

Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free