LESSON 296 OF 414 · BACKTRACKING

Binary Strings With K Ones in Rust: Recursive 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: [
    "0011",
    "0101",
    "0110",
    "1001",
    "1010",
    "1100"
]

Notes: K <= N <= 20

STEP 1 OF 10

Guided

Ctrl + Enter to check

RUST · BACKTRACKING

Generate Binary Strings With K Ones in Rust, explained

Problem overview

The function generate_binary_strings takes two non-negative integers, n and k, with k <= n <= 20. It returns every binary string of length n that contains exactly k ones, as a Vec<String>.

For n = 4 and k = 2 there are six such strings: 1100, 1010, 1001, 0110, 0101 and 0011. The reference solution produces them in ascending order, starting with 0011, because it tries '0' before '1' at every position.

Approach: decide one position at a time

Every string is a sequence of n choices, each '0' or '1'. A recursive function builds a prefix: at each call it appends '0' and recurses, then appends '1' and recurses. That is a binary tree of depth n whose leaves are all the strings.

To keep only the strings with k ones, the function carries k as a budget: the number of ones still to place. Appending '1' spends one, appending '0' spends none. When the prefix reaches length n, the string is an answer exactly when the budget is 0. A negative budget means too many ones have been placed, so that branch stops at once.

Take n = 3 and k = 1. The calls "", "0" and "00" each branch twice. "000" is full length with a budget of 1, so it is dropped. "001" is full length with a budget of 0, so it is kept. The answers are 001, 010 and 100.

The check for too few ones happens only at full length. That is simple and correct, though it explores some branches that can't succeed.

Step by step

Create solutions as an empty mutable vector. The helper pushes into it, and the compiler infers the element type.
Start the recursion with Self::gen: an empty String, then n, k and &mut solutions. Since gen belongs to Solution, it's called as Self::gen.
Return solutions as the final expression. A trailing semicolon would turn it into a statement and the function would return ().
Declare gen with the prefix, n, the remaining ones k and the output vector.
Stop when k < 0. That branch has already used more ones than allowed.
Detect a full-length prefix by comparing current.len() as i32 with n.
Keep it only if k == 0, then return in every full-length case. A string of length n is never extended.
Append '0' to a clone of current and recurse with the same k.
Append '1' to current itself and recurse with k - 1.

The solution in Rust

impl Solution {
    fn generate_binary_strings(n: i32, k: i32) -> Vec<String> {
        let mut solutions = Vec::new();
        Self::gen(String::new(), n, k, &mut solutions);
        solutions
    }

    fn gen(current: String, n: i32, k: i32, solutions: &mut Vec<String>) {
        if k < 0 {
            return;
        }
        if current.len() as i32 == n {
            if k == 0 {
                solutions.push(current);
            }
            return;
        }
        let mut c0 = current.clone();
        c0.push('0');
        Self::gen(c0, n, k, solutions);
        let mut c1 = current;
        c1.push('1');
        Self::gen(c1, n, k - 1, solutions);
    }
}

The Rust details worth a closer look:

Different integer types. String::len returns a usize, while n is an i32. Rust refuses to compare them directly, so the code casts the length with as i32. For lengths up to 20 that loses nothing.
Clone, then move. The '0' branch needs current to survive for the '1' branch, so it works on current.clone(). The '1' branch is the last use, so let mut c1 = current; moves the string with no copy. Using current after that line would be a compile error.
Taking a prefix by value. Because each call owns its string, no call can change the prefix of its caller. There is no need to remove the last character after a recursive call, which other languages need when they share one buffer.
Passing the output vector. solutions has type &mut Vec<String> inside gen, so the recursive calls hand it on by name and the same vector receives every answer.
Pushing moves the string. solutions.push(current) gives ownership of the string to the vector, and the return right after means it is never used again.

Complexity

Time. In the worst case the recursion tree has about 2^(n+1) calls, and most calls copy a string of up to n characters, so the bound is O(n * 2^n). The k < 0 check removes branches that hold too many ones, but branches with too few ones are only discovered at full length. The number of answers is the binomial coefficient C(n, k). For n = 20 and k = 10 that is 184756 strings.

Space beyond the output. The recursion is at most n deep, and each live call can hold a string of up to n characters, so about O(n^2). The output itself takes O(n * C(n, k)).

Edge cases and common mistakes

k = 0. The only answer is a string of zeros: n = 3 gives ["000"].
k = n. The only answer is all ones.
k > n. It's outside the stated limits, but the code handles it: n = 2, k = 3 gives an empty vector, because no full-length string reaches a budget of exactly 0.
n = 0. The empty prefix already has length 0, so n = 0, k = 0 returns a vector holding one empty string.
Checking k only at the end. Without the k < 0 check the program still gives the right answer, but it explores every one of the 2^n strings.
Forgetting the return after the length check. The recursion would continue past length n and never end.
Expecting the example's order. The strings come out in ascending order, not in the order the example lists them.

Testing

n = 4, k = 2 gives ["0011", "0101", "0110", "1001", "1010", "1100"].
n = 3, k = 0 gives ["000"].
n = 2, k = 3 gives [].
n = 0, k = 0 gives [""].
n = 20, k = 10 gives 184756 strings.

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

Start learning free