Generate all binary code strings with length K

Today’s practice algorithm question is to generate all binary code string with K. Let’s begin!

Problem

Given an integer K, return a list of all possible binary code string with length K.

Binary code string is a string containing only "0" and "1". The order of the return list does not matter.

For example:

Example 1

Input: k = 1
Output: ["0", "1"]

Example 2

Input: k = 2
Output: ["00", "01", "10", "11"]

Analysis

As you can see, the problem contains two sub-problems, which is, a string with length k can be generated from either:

• a string with length k - 1 and appending "0".
• a string with length k - 1 and appending "1".

So with a simple recursion, we can make it work.

Solution

This is the solution in Java.

public List generate(int k) {
    List res = new LinkedList<>();
    generate(k, 0, "", res);

    return res;
}

public void generate(int k, int i, String s, List res) {
    if (i == k) {
        res.add(s);
        return;
    }

    generate(k, i + 1, s + "0", res);
    generate(k, i + 1, s + "1", res);
}

Have fun !