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

Objective: Given an array of integers of size N, print all the subsets of size k. (k<=N)

Example:

Generate all subsets of a fixed size k of a given set [1,2,3…n]. e.g, if n=5 and k=3, the output 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:

• Create an boolean array of the same size as the given array.
• Now for every integer 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 corresponding index or if we ignore it, put FALSE at that index.
• We will start with currentLength =0 and do the recursive calls for both the options mentioned in the previous step.
• If we select an integer to print, make currentLength +1 and if we ignore, dont change currentLength.
• Another important factor is from which index you will start making the subset of size k. Initialize start = 0, and with every recursive call, make start + 1 ( for both the scenarios mentioned in the steps above).
• Print the elements when currentLength = k.

Note: Click on the image to enlarge it.

Complete Code:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 public class AllSubSetOfSizeK { public void subset(int[] A, int k, int start, int currLen, boolean[] used) { if (currLen == k) { for (int i = 0; i < A.length; i++) { if (used[i] == true) { System.out.print(A[i] + " "); } } System.out.println(); return; } if (start == A.length) { return; } // For every index we have two options, // 1.. Either we select it, means put true in used[] and make currLen+1 used[start] = true; subset(A, k, start + 1, currLen + 1, used); // 2.. OR we dont select it, means put false in used[] and dont increase // currLen used[start] = false; subset(A, k, start + 1, currLen, used); } public static void main(String[] args) { int A[] = { 1, 2, 3, 4, 5 }; boolean[] B = new boolean[A.length]; AllSubSetOfSizeK i = new AllSubSetOfSizeK(); i.subset(A, 3, 0, 0, B); } }

```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

```