Problem overview
The method generateBinaryStrings takes two integers, n and k, and returns every binary string of length n that contains exactly k ones. The result is an ArrayBuffer[String], and the constraint is k <= n <= 20.
For n = 4 and k = 2 there are six such strings: 0011, 0101, 0110, 1001, 1010 and 1100. The method returns them in this order, the order you get by comparing the strings as text from smallest to largest. The number of results is always "n choose k", so 6 for this example and 184756 for n = 20, k = 10.
Approach: build the string one character at a time
Checking all 2^n strings and counting their ones would work, but it wastes effort on strings that went wrong early. Backtracking builds each string from left to right instead. At every position it has two choices, a '0' or a '1', and it explores both with a recursive call. Each call receives the prefix built so far and the number of ones it is still allowed to place.
That budget makes the search cheap. Placing a '1' spends one unit of it. When the budget goes below zero, the prefix already has too many ones, and no way of finishing it can fix that, so the whole branch is dropped without looking at the characters that would follow. When the prefix reaches length n, the string is complete, and it is valid only if the budget is exactly zero: any budget left means the string has too few ones.
Trying '0' before '1' at every position is what makes the results come out in ascending order.
Step by step
- Declare a shared
solutionsfield of typeArrayBuffer[String], avarstarting asnull. The recursive helper andgenerateBinaryStringsboth need to reach the collected strings, so it lives in the class rather than being passed around. - Reset it at the start of the method with a fresh empty
ArrayBuffer[String](). Results from an earlier call can't leak into the next one. - Start the recursion with an empty prefix
"", the target lengthnand the full budgetk, then returnsolutions. - Declare the helper
generatewith the parameterscurrent,nandk, returningUnit. Herekis the number of ones that may still be placed. - Prune when
kis-1. This happens the moment one'1'too many is placed. Becausekdrops by exactly one per call, it can never skip over-1. - Check whether
currenthas lengthn. A full-length string must be judged, never extended. - Record it only when
k == 0, then return in both cases, so the recursion never grows a string past the target length. - Recurse with
'0'appended andkunchanged, since a zero costs nothing. - Recurse with
'1'appended andk - 1, since a one spends part of the budget.
The solution in Scala
class Solution {
def generate(current: String, n: Int, k: Int): Unit = {
if (k == -1) {
return
}
if (current.length == n) {
if (k == 0) {
solutions += current
}
return
}
generate(current + '0', n, k)
generate(current + '1', n, k - 1)
}
var solutions: ArrayBuffer[String] = null
def generateBinaryStrings(n: Int, k: Int): ArrayBuffer[String] = {
solutions = ArrayBuffer[String]()
generate("", n, k)
return solutions
}
}
The Scala details worth a closer look:
ArrayBufferis mutable. It comes fromscala.collection.mutable, and+=appends an element to it in place. A plainListwould be immutable, so every addition would have to produce a new list.current + '0'builds a new string. Scala strings are immutable Java strings, and+with aCharreturns a fresh one.currentitself doesn't change, so the next line can append'1'to the same prefix. This is why the code needs no explicit "undo" step, even though the technique is called backtracking.lengthhas no parentheses.current.lengthis how you read a string's size in Scala.returnin aUnitmethod. A barereturnleaves the method early. In Scala it is more common to let the last expression be the value, but early returns for base cases read well in a recursive helper.- The field is shared state. Because
solutionsis avaron the object, two threads callinggenerateBinaryStringson the sameSolutionwould trample each other. For a single-threaded lesson it is fine, and the reset at the start keeps repeated calls independent.
Complexity
Time: every call either stops or adds one character, so the recursion tree has depth at most n. Pruning keeps it from reaching all 2^n leaves. A prefix survives while it has at most k ones, so the work is bounded by the number of such prefixes, times O(n) for building each string. In the worst case this is still exponential, and for small k it is much smaller than 2^n.
Space: the recursion uses O(n) stack frames, each holding a string of up to n characters, so O(n^2) characters at the deepest point. The output itself is C(n, k) * n characters, which dominates for larger inputs.
Edge cases and common mistakes
k = 0. Only the all-zero string qualifies:n = 3,k = 0gives["000"], because the first'1'immediately drives the budget to-1.k = n. Only the all-one string qualifies:n = 3,k = 3gives["111"].n = 0. The empty prefix already has length 0, so withk = 0the result holds a single empty string.- Accepting short budgets. Recording a string without testing
k == 0would include strings with too few ones, such as"0001"fork = 2. - Forgetting the return after the length check. The recursion would keep appending characters to full-length strings and never finish.
- Sharing one buffer between calls. If
solutionswere created once and never reset, a second call would return the first call's strings as well.
Testing
n = 4,k = 2gives0011, 0101, 0110, 1001, 1010, 1100.n = 3,k = 0gives000.n = 3,k = 3gives111.n = 5,k = 2gives 10 strings.n = 20,k = 10gives 184756 strings.
