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

Print All Combinations of subset of size K from Given Array

Objec­tive: Given an array of inte­gers of size N, print all the sub­sets of size k. (k<=N)

Exam­ple:

Gen­er­ate all sub­sets of a fixed size k of a given set [1,2,3…n]. e.g, if n=5 and k=3, the out­put will look like

1 2 3     1 2 4     1 2 5
1 3 4     1 3 5     1 4 5
2 3 4     2 3 5     2 4 5
3 4 5

Approach:

  • Cre­ate an boolean array of the same size as the given array.
  • Now for every inte­ger we have two options, whether to select it or ignore it.
  • Now if we select it, we will put TRUE in the boolean array at the cor­re­spond­ing index or if we ignore it, put FALSE at that index.
  • We will start with cur­rentLength =0 and do the recur­sive calls for both the options men­tioned in the pre­vi­ous step.
  • If we select an inte­ger to print, make cur­rentLength +1 and if we ignore, dont change currentLength.
  • Another impor­tant fac­tor is from which index you will start mak­ing the sub­set of size k. Ini­tial­ize start = 0, and with every recur­sive call, make start + 1 ( for both the sce­nar­ios men­tioned in the steps above).
  • Print the ele­ments when cur­rentLength = k.

Note: Click on the image to enlarge it.

Print-All-Combinations-of-subset-of-size-K-from-Given-Array

Print-All-Combinations-of-subset-of-size-K-from-Given-Array

Com­plete Code:

Output:
1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5 

You may also like...

  • Agnos­tic

    Nicely explained indeed!, but this is expo­nen­tial solu­tion can we do bet­ter than this?