LESSON 263 OF 338 · BACKTRACKING

Generate Binary Strings With K Ones in Go: 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 10

Guided

Ctrl + Enter to check

GO · BACKTRACKING

Generate Binary Strings With K Ones in Go, explained

Problem overview

The function generateBinaryStrings receives two non-negative integers, n and k, and returns every binary string of length n that contains exactly k ones. The lesson guarantees k <= n and n <= 20.

For n = 4 and k = 2 there are six strings: 0011, 0101, 0110, 1001, 1010 and 1100. That count is the number of ways to choose which 2 of the 4 positions hold a one: 4 choose 2 = 6.

Approach: decide one character at a time

Building a string from left to right means making n decisions, each 0 or 1. This is a binary decision tree of depth n. Its leaves are all 2^n strings, and only those with exactly k ones are answers.

The recursion carries a budget: onesLeft, the number of ones the string may still receive. Writing a 0 leaves the budget alone, and writing a 1 spends one unit. Two outcomes follow:

If the budget goes below zero, the prefix already has too many ones. No continuation can repair that, so the branch stops.
If the string reaches length n, it is an answer exactly when the budget is zero. A positive leftover means the string has too few ones.

Counting down a budget avoids counting the ones in the string again at every step. The recursion needs only the prefix, the target length and the budget.

Here is one branch for n = 3 and k = 1. Start with prefix "" and budget 1. Choosing 1 gives prefix "1" with budget 0. Choosing 0 twice gives "100", which has length 3 and budget 0, so it is recorded. The branch that picks a second 1 from "1" reaches budget -1 and stops immediately. Another branch, "000", reaches full length with budget 1 and is discarded. The answers are 001, 010 and 100.

Step by step

Create the result slice. solutions is an empty []string inside generateBinaryStrings.
Start the recursion with an empty prefix, n, k as the initial budget and the address of solutions.
Return the slice after the recursion finishes.
Declare the helper generateBinaryString taking current string, n, onesLeft int and solutions *[]string.
Reject over-spent branches: return at once when onesLeft is negative.
Handle full-length strings. When len(current) == n, append the string only if onesLeft == 0, then return in either case, so no string grows beyond n characters.
Extend with a zero, leaving the budget unchanged.
Extend with a one, passing onesLeft-1.

The solution in Go

func generateBinaryStrings(n, k int) []string {
	solutions := []string{}
	generateBinaryString("", n, k, &solutions)
	return solutions
}

func generateBinaryString(current string, n, onesLeft int, solutions *[]string) {
	if onesLeft < 0 {
		return
	}
	if len(current) == n {
		if onesLeft == 0 {
			*solutions = append(*solutions, current)
		}
		return
	}
	generateBinaryString(current+"0", n, onesLeft, solutions)
	generateBinaryString(current+"1", n, onesLeft-1, solutions)
}

The Go details worth knowing:

The slice pointer. The helper receives *[]string and runs *solutions = append(*solutions, current). A slice passed by value is a copy of its header (pointer, length, capacity), so an append inside the helper would be invisible to the caller once the array is reallocated. Passing &solutions lets every call update the same slice.
String concatenation. current+"0" creates a new string, and current itself doesn't change. The second recursive call therefore starts from the same prefix without any undo step.
One return for two cases. The return sits after the inner if, not inside it. That is what makes full-length strings with the wrong number of ones stop too, instead of falling through to the recursive calls.
Bytes. len(current) is the number of bytes. For a string of 0 and 1 characters, bytes and characters are the same thing.
Order. Trying "0" before "1" yields the strings in ascending dictionary order, so 0011 comes first and 1100 last.

Complexity

Time: the recursion can visit every prefix that has at most k ones, so in the worst case it explores close to 2^n branches, and building each string costs up to O(n). The reference doesn't prune a prefix that has too few ones for the positions left, such as 000 when n = 4 and k = 2; it discovers the problem only at full length. Adding a check that onesLeft doesn't exceed n - len(current) would remove those dead ends. For n = 20, the unpruned version is still fast.

Space: the recursion is n calls deep. The result itself holds C(n, k) strings of length n, which for n = 20 and k = 10 is 184,756 strings.

Edge cases and common mistakes

k = 0. The only answer is a string of n zeros. generateBinaryStrings(3, 0) gives [000].
k = n. The only answer is a string of n ones.
n = 0. The prefix is already at the target length and the budget is zero, so the answer is a slice holding one empty string.
k greater than n. The constraints rule it out. If it happened, no string could spend the whole budget, and the result would be empty.
Appending without the pointer. Writing solutions = append(solutions, current) inside the helper updates only a local copy, and the caller receives an empty slice.
Accepting leftover budget. Appending every full-length string without checking onesLeft == 0 returns strings with fewer than k ones.
Forgetting the return after the length check. The recursion would keep extending strings past length n and never stop.

Testing

generateBinaryStrings(4, 2) gives [0011 0101 0110 1001 1010 1100] when printed with fmt.Println.
generateBinaryStrings(3, 0) gives [000].
len(generateBinaryStrings(20, 10)) is 184756.

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

Start learning free