Problem overview
The method generateBinaryStrings(_ n: Int, _ k: Int) returns every binary string of length n that contains exactly k ones, as a [String]. The constraints are k <= n <= 20.
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 number of results is the binomial coefficient "n choose k", which is 6 here and 184756 for n = 20, k = 10.
Approach: build each string one character at a time
A brute-force idea is to generate all 2^n strings and keep the ones with the right number of ones. For n = 20 that is over a million strings, most of them thrown away. Backtracking does better: it builds a string from left to right, and gives up on a partial string as soon as it can no longer lead to a valid answer.
At every position there are two choices, append "0" or append "1". The recursion carries three things: the prefix built so far (current), the target length (n) and the number of ones it may still place (k). Appending a "1" spends one unit of that budget, while appending a "0" costs nothing.
That gives two rules for stopping:
- If
kdrops to-1, the prefix already holds more ones than allowed, so no extension can fix it. The whole branch is cut off. - If the prefix has reached length
n, it is complete. It is a valid answer only whenkis exactly 0, which means the budget was fully used.
Trying "0" before "1" at each position produces the results in ascending (lexicographic) order, so for n = 4, k = 2 the method returns ["0011", "0101", "0110", "1001", "1010", "1100"].
Step by step
- Declare a
solutionsfield in the class, of type[String]!. BothgenerateBinaryStringsand the recursive helper need to reach the collected strings, and a property of the class is visible to every method. - Reset it at the start of
generateBinaryStringsby assigning[]. The sameSolutionobject can be used for several calls, and the old results must not leak into a new call. - Start the recursion with
generate("", n, k): an empty prefix, the target length and the full budget. - Return
solutionsonce the recursion has finished filling it. - Declare the helper
generate(_ current: String, _ n: Int, _ k: Int). The underscores drop the argument labels, so calls readgenerate("", n, k). - Prune with
if k == -1 { return }. One1too many has been placed. - Check for a full string with
current.count == n. A string of full length is judged, never extended. - Record it only if
k == 0. Leftover budget means the string has too few ones. - Return from inside the length check, whether or not the string was recorded, so the recursion never grows a string past
n. - Recurse with
"0":generate(current + "0", n, k), with the budget unchanged. - Recurse with
"1":generate(current + "1", n, k - 1), which spends one unit.
The solution in Swift
class Solution {
func generate(_ current: String, _ n: Int, _ k: Int) {
if k == -1 {
return
}
if current.count == n {
if k == 0 {
solutions.append(current)
}
return
}
generate(current + "0", n, k)
generate(current + "1", n, k - 1)
}
var solutions: [String]!
func generateBinaryStrings(_ n: Int, _ k: Int) -> [String] {
solutions = []
generate("", n, k)
return solutions
}
}
Swift details worth a closer look:
[String]!is an implicitly unwrapped optional. The property starts asniland has no value untilgenerateBinaryStringsassigns[]. After that, the code can callsolutions.append(current)andreturn solutionswithout writing?or!each time. The price is that reading it while it is stillnilcrashes the program, which is why the method assigns it before the first use.- Strings are values.
current + "0"builds a new string and leavescurrentunchanged, so the next line can still use the original prefix for the"1"branch. This is what makes the backtracking work without any undo step. countcounts characters. A SwiftStringhas nolengthproperty.current.countwalks the string to count its characters, which is fine for strings of at most 20 characters.- Methods can use properties declared later.
generateusessolutionseven though the property is declared below it. Inside a class, the order of members doesn't matter. - Labels. Without the underscores, a call would have to be written
generate(current: "", n: n, k: k).
Complexity
Time. The recursion explores a tree whose nodes are valid or still-promising prefixes. A prefix that has already used more than k ones is cut immediately, but a prefix with too few ones is still extended, and this lesson's version doesn't check whether enough positions remain to place the missing ones. In the worst case, the tree therefore has O(2^n) nodes, each building a string of up to n characters, which is O(n * 2^n). For n = 20 that is still comfortably fast.
Space. The recursion is at most n + 1 calls deep. The output itself needs C(n, k) strings of length n, and that dominates.
Edge cases and common mistakes
k = 0. The only answer is the all-zero string:generateBinaryStrings(3, 0)returns["000"].k = n. The only answer is all ones:generateBinaryStrings(3, 3)returns["111"].n = 0. Withk = 0the empty string already has length 0 and an empty budget, so the result is[""], a list holding one empty string.- Not resetting
solutions. Calling the method twice on the same object would return the first call's strings mixed into the second call's result. - Forgetting the
returnafter the length check. The recursion would keep extending strings that are already complete, and it would never stop. - Accepting strings without checking
k == 0. Forn = 2,k = 1, the string"00"has full length but too few ones, and must be rejected.
Testing
n = 4,k = 2gives["0011", "0101", "0110", "1001", "1010", "1100"].n = 2,k = 1gives["01", "10"].n = 3,k = 0gives["000"].n = 3,k = 3gives["111"].n = 0,k = 0gives[""].n = 20,k = 10returns 184756 strings.
