Challenge 09: Binary Strings

Before deciding going to CMU for graduate school, Cat was considering selling out and getting a real job out in industry. To do so, however, she had to pass the dreaded programming interviews. In one of her first interviews, she faced the following problem:

Given a length N and a count K, generate all the binary strings with exactly K 1's.  You will need to support binary strings of 1 <= N <= 16.

Being a noob at the time ¹, she failed and didn't pass the interview ². Her failure on this interview question haunts her to this day ³.

This is your opportunity to show that you are just as good as a CMU graduate student and solve this problem for Cat once and for all.

Input

You will be given a series of inputs where each line specifies N (length of binary string) and K (the number of 1s in the binary string):

Example Input

4 3
4 4

Output

For each pair of N and K inputs, print out all the binary strings with length N that contain exactly K 1s. If there is more than one binary string, then display them in lexigraphical order.

Example Output

0111
1011
1101
1110

1111

Submission

To submit your work, follow the same procedure you used for Reading 00:

$ cd path/to/cse-30872-fa20-assignments     # Go to assignments repository
$ git checkout master                       # Make sure we are on master
$ git pull --rebase                         # Pull any changes from GitHub

$ git checkout -b challenge09               # Create and checkout challenge09 branch

$ $EDITOR challenge09/program.cpp           # Edit your code

$ git add challenge09/program.cpp           # Stage your changes
$ git commit -m "challenge09: done"         # Commit your changes

$ git push -u origin challenge09            # Send changes to GitHub

To check your code, you can use the .scripts/submit.py script or curl:

$ .scripts/submit.py
Submitting challenge09 assignment ...
Submitting challenge09 code ...
  Result Success
   Score 6.00
    Time 0.52

$ curl -F source=@challenge09/program.cpp https://dredd.h4x0r.space/code/cse-30872-fa20/challenge09
{"result": "Success", "score": 6, "time": 0.5163395404815674}