Reference no: EM132931364

Assignment 1: Write code to build explicitly all combinations of k 1s in n boxes
k=4, n=12

Recursion: Invoke fun(0.-1)

Define fun(bit_num, prev_bit_pos):
1) If bit_num-k,
(a) Print current combination;
(b) return (exit);

2) Otherwise
for(i-prev_bit_pos+1, i<=n-k+bit_num, i++){
(a) Place 1 at position i;
(b) invoke fun(bit_num+1,1);
(c) clear bit at position i;}

Iteration:
1) Consider all integer numbers from 0 to 2"n-1
2) Convert each int number to binary form
3) Compute the popcount (no. of 1s)
4) If popcount-k. this is one of the desired combination

Complexity: O(2^n)

Complexity: O(n! /( k!(n - k)!)))