LESSON 269 OF 348 · BACKTRACKING

Binary Strings with K Ones in TypeScript: 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

TYPESCRIPT · BACKTRACKING

Generate Binary Strings With K Ones in TypeScript, explained

Problem overview

The method generateBinaryStrings receives two non-negative integers, n and k, with k <= n and n at most 20. It returns every binary string of length n that contains exactly k ones, as an array of strings.

For n = 4 and k = 2 there are six such strings: 0011, 0101, 0110, 1001, 1010 and 1100. Each is a different way to choose which two of the four positions hold a 1, and there are "4 choose 2" = 6 ways.

Approach: build one character at a time with a budget

There are 2^n binary strings of length n. Generating them all and counting the ones in each would work, but backtracking lets the search drop bad strings early.

Build each string character by character. At each position there are two choices, '0' or '1'. Carry a number, k, that says how many ones may still be placed. Appending '0' leaves it unchanged. Appending '1' spends one, so the next call gets k - 1.

If k reaches -1, the prefix holds one more 1 than allowed. Nothing it grows into can be valid, so stop.
When the string reaches length n, it is valid only if the budget is spent exactly, that is, k == 0. A leftover budget means the string has too few ones.

Trying '0' before '1' makes the results come out in increasing order, 0011 first and 1100 last.

Step by step

Reset the results. At the top of generateBinaryStrings, set this.solutions to an empty array. The class declares solutions: string[]; because TypeScript requires every property to be declared.
Start the recursion with an empty prefix "", the length n and the full budget k.
Return this.solutions.
Declare generate with current: string, n: number and k: number: the prefix built so far, the target length and the ones still allowed.
Prune by returning as soon as k is -1.
Check the length. When current.length == n, the string is complete. length is a property, so there are no parentheses.
Keep it only if k == 0, and push it onto this.solutions.
Return after a complete string, whether it was kept or not, so strings never grow past n.
Append '0', keeping k the same.
Append '1', passing k - 1.

The solution in TypeScript

class Solution {
    solutions: string[];
    generate(current: string, n: number, k: number) {
        if (k == -1) {
            return;
        }
        if (current.length == n) {
            if (k == 0) {
                this.solutions.push(current);
            }
            return;
        }
        this.generate(current + '0', n, k);
        this.generate(current + '1', n, k - 1);
    }

    generateBinaryStrings(n: number, k: number): string[] {
        this.solutions = [];
        this.generate("", n, k);
        return this.solutions;
    }
}

Tracing n = 2, k = 1: the first call has prefix "" and budget 1. Its '0' branch has prefix "0" and budget 1, which then makes "00" with budget 1 (rejected, one 1 still owed) and "01" with budget 0 (kept). Its '1' branch has prefix "1" and budget 0, which makes "10" with budget 0 (kept) and "11" with budget -1 (pruned immediately). The result is ["01", "10"].

The search could also stop earlier on the other side: if the number of positions still to fill, n - current.length, is smaller than k, the prefix can no longer reach exactly k ones. The lesson skips that check, because with n at most 20 the simpler code is fast enough, but it is the natural next improvement. It would cut the 2.1 million calls for n = 20, k = 20 down to about 40.

TypeScript details worth knowing:

Strings are immutable. current + '0' builds a new string and leaves current unchanged, so the next line can still use current. No undo step is needed.
Results are strings, not numbers. "0011" keeps its leading zeros, which a number could not.
Shared field. this.solutions is visible in every method of the object, so the helper can push into it without returning anything. It is reset on each call to generateBinaryStrings.
Inferred void. generate returns nothing, and TypeScript works out the return type by itself.

Complexity

The answer contains "n choose k" strings, each of length n. For n = 20 and k = 10 that is 184,756 strings.

Time: O(2^n * n) in the worst case. The search tree has up to 2^(n+1) nodes, and each node builds a string of up to n characters. The pruning only cuts branches with too many ones. Branches with too few are explored to full length and rejected there. In a test run, n = 20, k = 10 made about 1.6 million calls to produce 184,756 results, and n = 20, k = 20 made about 2.1 million calls to produce a single string. Both finish quickly, since n is at most 20.

Space: the results take O(n) per string. The recursion is n levels deep.

Edge cases and common mistakes

k = 0. The only answer is n zeros: "000" for n = 3.
k = n. The only answer is n ones: "111" for n = 3.
n = 0. The empty string has no ones, so k = 0 gives [""].
k greater than n. The statement rules this out. If it happened, no string could use enough ones, and the result would be [].
Forgetting the exact check. If the length check accepts every full-length string, strings with too few ones slip through. The test is k == 0, not k >= 0.
Forgetting to return after a full string. Without the return, the function would keep appending characters past length n.
Spending the budget on zeros. Only the '1' branch passes k - 1.

Testing

n = 4, k = 2 gives ["0011", "0101", "0110", "1001", "1010", "1100"]. Any order is a correct set; this solution produces this one.
n = 3, k = 1 gives ["001", "010", "100"].
n = 3, k = 0 gives ["000"].
n = 3, k = 3 gives ["111"].
n = 1, k = 1 gives ["1"].

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

Start learning free