Problem overview
Given two non-negative integers n and k, generateBinaryStrings returns every binary string of length n that contains exactly k ones. The lesson states k <= n <= 20.
For n = 4 and k = 2 there are six strings: 0011, 0101, 0110, 1001, 1010 and 1100. The result in this solution comes out in this order, smallest first. The order of the result is not what matters, only that each string appears once.
Approach
Build the string from left to right. At each position we choose '0' or '1', which gives a binary tree of choices with depth n. A leaf at depth n is a complete string, and we keep it only if it has exactly k ones.
To count the ones without scanning each string, pass a budget k down the recursion: the number of ones we may still place. Appending '0' leaves the budget as it is. Appending '1' spends one, so the budget becomes k - 1. Then:
- if the budget drops to
-1, we have placed too many ones, so the whole branch is abandoned; - if the string reaches length
nwith a budget of exactly0, it holds exactlykones and is a result; - a full-length string with budget above 0 has too few ones and is discarded.
Step by step
- A shared list.
solutionsis alateinit varof typeMutableList<String>. It has no value untilgenerateBinaryStringsruns, which is exactly whatlateinitis for. - Reset it. At the top of
generateBinaryStrings, assignmutableListOf(). The element type is inferred from the property's declared type, and a fresh list keeps old results out. - Start the recursion with
generate("", n, k): an empty prefix, the target length and the full budget. Then returnsolutions. - Declare
generatewithcurrent: String,n: Intandk: Int. - Prune. If
k == -1, return: this branch already has one '1' too many. - Handle a full string. If
current.length == n, addcurrenttosolutionsonly whenk == 0, and return in either case so a string never grows beyondncharacters. In Kotlinlengthis a property, written without parentheses. - Branch. Recurse with
current + '0'and the samek, then withcurrent + '1'andk - 1. Trying'0'first produces the strings in increasing order.
The solution in Kotlin
class Solution {
fun generate(current: String, n: Int, k: Int) {
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)
}
lateinit var solutions: MutableList<String>
fun generateBinaryStrings(n: Int, k: Int): List<String> {
solutions = mutableListOf()
generate("", n, k)
return solutions
}
}
Kotlin details:
current + '0'creates a new string and leavescurrentunchanged. That is why the second recursive call can usecurrentagain, and why there is no undo step.- Chars and strings.
'0'is aCharand"0"is aString. Adding aCharto aStringwith+appends the character, so"ab" + '0'is"ab0". It is not arithmetic: nothing is added numerically. lateinit varreads like a normal property but has no starting value. Reading it too early throwsUninitializedPropertyAccessException.- Return type. The function returns
List<String>. TheMutableListstored insolutionsis also aList, so it can be returned as it is. - Early
return. A barereturnleaves a function that returnsUnit, which is the default when you write no return type.
Following n = 3, k = 1
The search starts from the empty string with a budget of 1. Appending '0' three times gives 000 with budget 1, which is discarded because the budget is not 0. Backing up one level, 00 followed by '1' gives 001 with budget 0, which is kept. The branch 01 continues with '0' to reach 010, kept, while 011 brings the budget to -1 and is cut at once. The branch 1 has budget 0, so only the zeros after it survive and 100 is kept. The result is ["001", "010", "100"].
Complexity
The recursion tree has up to 2^n leaves, because for each of the n positions we try both characters. The budget check cuts only branches with too many ones, so the search still visits strings with too few ones and discards them at the end. Each leaf costs O(n) to build. For n = 20 that is at most about a million leaves. The result list holds C(n, k) strings of length n, for example 184756 strings for n = 20 and k = 10. The recursion is n levels deep.
A tighter version would also stop a branch when the budget is larger than the number of positions left, because such a branch can never reach exactly k ones. The lesson's version keeps the code simple.
Edge cases and common mistakes
- k = 0. There is exactly one string, all zeros.
generateBinaryStrings(3, 0)returns["000"]. - k = n. Exactly one string, all ones:
generateBinaryStrings(3, 3)returns["111"]. - k larger than n. The lesson rules it out, but the code handles it: no string can match, and
generateBinaryStrings(2, 5)returns an empty list. - n = 0. The empty string has length 0 and, with
k = 0, matches, so the result is a list holding one empty string. - Accepting a full string with a leftover budget. Without the
k == 0check, you would also return strings with too few ones. - Forgetting to return after the length check. The string would keep growing past length
n, and the recursion would never end. - Forgetting the reset. A second call would return the earlier strings along with the new ones.
Testing
generateBinaryStrings(4, 2)returns["0011", "0101", "0110", "1001", "1010", "1100"].generateBinaryStrings(3, 0)returns["000"].generateBinaryStrings(3, 3)returns["111"].generateBinaryStrings(20, 10).sizeis 184756.