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 1, she failed and didn't pass the interview 2. Her failure on this interview question haunts her to this day 3.

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.


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


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.

Note: Separate test cases by placing a blank line between them as shown below.

Example Output




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

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

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

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

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

$ git push -u origin challenge10            # Send changes to GitLab

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

$ .scripts/
Submitting challenge10 assignment ...

Submitting challenge10 code ...
  Result Success
   Score 6.00
    Time 0.92

$ curl -F source=@challenge10/program.cpp
{"score": 6, "result": "Success"}

Once you have commited your work and pushed it to GitLab, member to create a merge request. Refer to the Reading 05 TA List to determine your corresponding TA for the merge request.

  1. She is still a noob. <3. 

  2. Should have taken Programming Challenges... oh wait... ~RIP~. 

  3. Just like the time she casted a string into a double in Systems Programming. SMH