Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Reddit
Contact us
Hide Buttons

Generate all combinations of an array


 

Input :

[ 1, 2, 3 ]

 

Output :

[  ‘ ‘,  1,  2,  12,  3,  13,  23,  123  ]

 

Logic :

  • There are 2^n possible combinations for the array of size n
  • We have to generate binary code for all numbers from 0 to ( (2^n) – 1 )
  • For each binary code we need to generate corresponding number
  • For example, given array [ 1, 2, 3], we will generate binary code from 0 to 7
Input Binary Result
[ 1, 2, 3 ] 000 0
[ 1, 2, 3 ] 001 3
[ 1, 2, 3 ] 010 2
[ 1, 2, 3 ] 011 23
[ 1, 2, 3 ] 100 1
[ 1, 2, 3 ] 101 13
[ 1, 2, 3 ] 110 12
[ 1, 2, 3 ] 111 123

Execution steps

i j 2^j i & 2^j Binary decimal temp
0 0 1 0 0 0
1 2 0 0
2 4 0 0
1 0 1 1 1 1 1
1 2 0 0 1
2 4 0 0 1
2 0 1 0 0 2
1 2 2 1 2
2 4 0 0 2
3 0 1 1 1 3 1
1 2 2 1 12
2 4 0 0 12
4 0 1 0 0 4
1 2 0 0
2 4 4 1 3
5 0 1 1 1 5 1
1 2 0 0 1
2 4 4 1 13
6 0 1 0 0 6
1 2 2 1 2
2 4 4 1 23
7 0 1 1 1 7 1
1 2 2 1 12
2 4 4 1 123

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *