def subsets(n, k):
    assert k >= 0 and n >= 0
    if k == 0: # no students, all seats are empty
        yield '0'*n
    elif k == 1 and (n == 1 or n == 2): # the last student at the end of the row
        yield '1' + '0'*(n-1) # either '1' or '10'
        if n == 2: yield '01'
    elif n > 3*(k-1): # there are enough empty seats left for k students
        for s in subsets(n-3, k-1):
            yield '100' + s # place a student
        for s in subsets(n-1, k):
            yield '0' + s   # add empty seat
 
def isvalid(a, n, k):
    if not isinstance(a, basestring):
       a = ''.join(a) # `a` is a list of '1', '0'
    return (len(a) == n and a.count('1') == k and a.count('0') == (n-k) and
            all(p not in a for p in ['11', '101']))
 
 
n, k = 5, 2
for s in subsets(n, k):
    assert isvalid(s, n, k), s
    print(s)
 

ZGVmIHN1YnNldHMobiwgayk6CiAgICBhc3NlcnQgayA+PSAwIGFuZCBuID49IDAKICAgIGlmIGsgPT0gMDogIyBubyBzdHVkZW50cywgYWxsIHNlYXRzIGFyZSBlbXB0eQogICAgICAgIHlpZWxkICcwJypuCiAgICBlbGlmIGsgPT0gMSBhbmQgKG4gPT0gMSBvciBuID09IDIpOiAjIHRoZSBsYXN0IHN0dWRlbnQgYXQgdGhlIGVuZCBvZiB0aGUgcm93CiAgICAgICAgeWllbGQgJzEnICsgJzAnKihuLTEpICMgZWl0aGVyICcxJyBvciAnMTAnCiAgICAgICAgaWYgbiA9PSAyOiB5aWVsZCAnMDEnCiAgICBlbGlmIG4gPiAzKihrLTEpOiAjIHRoZXJlIGFyZSBlbm91Z2ggZW1wdHkgc2VhdHMgbGVmdCBmb3IgayBzdHVkZW50cwogICAgICAgIGZvciBzIGluIHN1YnNldHMobi0zLCBrLTEpOgogICAgICAgICAgICB5aWVsZCAnMTAwJyArIHMgIyBwbGFjZSBhIHN0dWRlbnQKICAgICAgICBmb3IgcyBpbiBzdWJzZXRzKG4tMSwgayk6CiAgICAgICAgICAgIHlpZWxkICcwJyArIHMgICAjIGFkZCBlbXB0eSBzZWF0CgpkZWYgaXN2YWxpZChhLCBuLCBrKToKICAgIGlmIG5vdCBpc2luc3RhbmNlKGEsIGJhc2VzdHJpbmcpOgogICAgICAgYSA9ICcnLmpvaW4oYSkgIyBgYWAgaXMgYSBsaXN0IG9mICcxJywgJzAnCiAgICByZXR1cm4gKGxlbihhKSA9PSBuIGFuZCBhLmNvdW50KCcxJykgPT0gayBhbmQgYS5jb3VudCgnMCcpID09IChuLWspIGFuZAogICAgICAgICAgICBhbGwocCBub3QgaW4gYSBmb3IgcCBpbiBbJzExJywgJzEwMSddKSkKCgpuLCBrID0gNSwgMgpmb3IgcyBpbiBzdWJzZXRzKG4sIGspOgogICAgYXNzZXJ0IGlzdmFsaWQocywgbiwgayksIHMKICAgIHByaW50KHMpCg==