Problem

Given an array of integers of size n, print or return all the subsets of size k. (k<=n)

Examples

Example 1:

1
2
3
4
5

Input: nums = [1, 2, 3, 4, 5], k = 3
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]]

Solutions

Method 1 - Recursion

This problem is similar to Subsets 1.

Algorithm

  • Boolean Array: Create a boolean array with the same length as the original array. This will track which elements are included in the current subset.
  • Recursive Choices: For each integer in the original array:
    • Include: Set the corresponding element in the boolean array to True.
    • Exclude: Set the corresponding element in the boolean array to False.
  • Recursive Calls: Make recursive calls for both options (include and exclude).
  • Current Length:
    • Include: If an integer is included, increment the currentLength by 1.
    • Exclude: If an integer is excluded, keep the currentLength unchanged.
  • Start Index: Track the starting index (start) for the current subset. Increment it (start + 1) with each recursive call (both options).
  • Print Subset: When the currentLength reaches the target size k, print the current subset based on the True elements in the boolean array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public void subsetsOfSizeK(int[] nums, int k) {
	dfs(nums, k, 0, 0, new boolean[nums.length]);
}
private void dfs(int[] nums, int k, int start, int currLen, boolean[] used) {
  if (currLen == k) {
    for (int i = 0; i < nums.length; i++) {
      if (used[i] == true) {
        System.out.print(nums[i] + " ");
      }
    }
    System.out.println();
    return;
  }

  if (start == nums.length) {
    return;
  }

  // For every index we have two options,
  // 1.. Either we include it, => put true in used[] and make currLen+1
  used[start] = true;
  subset(nums, k, start + 1, currLen + 1, used);
  // 2.. OR we exclude it, => put false in used[] and dont increase currLen
  used[start] = false;
  subset(nums, k, start + 1, currLen, used);
}