interview questions: find all numbers that contain k 1's

Question

I was asked to implement the following function:

void printNumber(int N, int K);

It prints all binary numbers of length N, which contains K ones.

e.g.

input: printNumber(3,2) 
output: 
011
101
110

I tried to solve this problem by manipulating the binary as string and used recursion, but I guess there are some bit operation trick that could solve this problem in a nicer way.

Any bit-magic I can apply here?

possible duplicate of [Generate all binary strings of length n with k bits set](http://stackoverflow.com/questions/1851134/generate-all-binary-strings-of-length-n-with-k-bits-set) — arshajii, Apr 26 '13 at 00:39

score 0 · Accepted Answer · answered Apr 26 '13 at 01:27

0

The best way is to generate them

   def go(n,k):
       if n == 0:
           if k > 0:
               return []
           if k == 0:
               return ['']

       return ['0'+x for x in go(n-1,k)] + ['1'+x for x in go(n-1,k-1)];

answered Apr 26 '13 at 01:27

dfb

13,133
2
31
52

score 0 · Answer 2 · answered May 10 '13 at 08:15

0

First find the binary value by using Integer.toBinaryString(i) and then take out the permutation of that value

answered May 10 '13 at 08:15

Code

184
1
8

interview questions: find all numbers that contain k 1's

2 Answers2