# 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:

 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

```

### 2 thoughts on “Print All Combinations of subset of size K from Given Array”

1. Nicely explained indeed!, but this is exponential solution can we do better than this?

2. 