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

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

what will be the time-complexity of this solution??