CODEWITHSUNDEEP
javascript
user2373804
user2373804

Reputation: 13

Combinations in recursive method

i have to print out the combinations of 0 and 1 if i have 3 digits, the output should be like this:

000 001 010 011 100 101 110 111

I know that involving the concept of 2^n, but i tried with many algorithms and logic and they didn't work out

This is what I have so far:

void combination( number)    {
    if(number == 0) {
        printf("\n");
        return;
    }
    combination(number - 1);
    printf("0");
    combination(number - 1);
    printf("1");
}

Upvotes: 0

Views: 88

Answers (2)

Tibos
Tibos

Reputation: 27853

As Yury mentioned, you don't need recursion (in fact if there is a recursive solution for a problem, there exists a non-recursive one as well!). But if you really want one, here it is:

// length is the length of the expected strings
// partial is a partial solution (a string with at most length characters)
// partial is not a required parameter!
function recursivePrint(length, partial) { 
  partial = partial || ''; // initialize partial to the empty string if it is not provided
  if (partial.length === length) { // exit condition
    console.log(partial); // a solution should be printed
  } else { // recursion incoming
    // the next step from a partial solution is to build 2 more (partial) solutions by appending 0/1 before this one
    recursivePrint(length, '0' + partial);
    recursivePrint(length, '1' + partial);
  }
}

recursivePrint(3); // start recursion

The steps it goes through:

''
'0'
'00'
'000' -> print
'100' -> print
'10'
'010' -> print
'110' -> print
'1'
'01'
'001' -> print
'101' -> print
'11'
'011' -> print
'111' -> print

TOTAL: 2^3 solutions

DEMO: http://jsbin.com/oBiMiHe/1/edit

Slightly improved, the recursivePrint function now gets a callback that gets called for each solution. The demo builds an array with the values which is then logged.

Upvotes: 1

Yury Tarabanko
Yury Tarabanko

Reputation: 45106

You don't actually need a recursion.

var print = function(num, digits) {
   var str = num.toString(2), diff = digits - str.length;
   return diff > 0 ? "0".repeat(diff) + str : str;
}, 
printAll = function(digits) {
   var i = 0, len = Math.pow(2, digits), result = [];
   for(; i < len; i++) {
     result.push(print(i, digits));
   }
   return result;
}

console.log(printAll(3))

Upvotes: 1

Related Questions