Challenge 08: 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 01:

$ cd path/to/cse-34872-su20-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 challenge08               # Create and checkout challenge08 branch

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

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

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

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

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

$ curl -F source=@challenge08/program.cpp https://dredd.h4x0r.space/code/cse-34872-su20/challenge08
{"result": "Success", "score": 6, "time": 0.5151612758636475}