Find all subsets of a fixed size k of the set [1, 2, 3... n]
  • Posted: 4 years ago
  • Updated: 3 years ago
  • Edit
  • answers (1)
  • views (7266)

Write a recursive function that generates 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

Like Find all subsets of a set [1,2,3...n] you can ignore the order in which the subsets are generated.


Posted Answers

To generate all subsets of size \( k \) of \( [1, 2, ..., n] \) , first put \( n \) into the current subset being generated and generate all subsets of size \( k-1 \) of \( [1, 2, ..., n-1] \). Then, skipping over element \( n \), generate all subsets of size \( k \) of \( [1, 2, ..., n-1] \).

public static void recursiveGenerateKSubsets(boolean[] subset, int n, int k){

/* Base case 1: When n = k, the entire set needs to be generated. Set the remaining elements true and print out the set */
if(n == k){
for(int i = 0; i < n; i++){
subset[i] = true;
printSubset(subset);
return;
}
}
/* Base case 2: Since k = 0, it means that the subset has been completely generated. Set the remaining elements false and print out the subset */
if (k == 0){
for(int i = 0; i < n; i++){
subset[i] = false;
printSubset(subset);
return;
}
}
/* Recursive case */
if(k > 0 & & n > k){
/* Recursive call 1 */
subset[n-1] = true;
recursiveGenerateKSubsets(subset, n-1, k-1);
/* Recursive call 2 */
subset[n-1] = false;
recursiveGenerateKSubsets(subset, n-1, k);
}
}

You need to Sign In to post your solution.