Find all subsets of length k in an array

Question

Given a set {1,2,3,4,5...n} of n elements, we need to find all subsets of length k .

For example, if n = 4 and k = 2, the output would be {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}.

I am not even able to figure out how to start. We don't have to use the inbuilt library functions like next_permutation etc.

Need the algorithm and implementation in either C/C++ or Java.

Answer 1

Recursion is your friend for this task.

For each element - "guess" if it is in the current subset, and recursively invoke with the guess and a smaller superset you can select from. Doing so for both the "yes" and "no" guesses - will result in all possible subsets.
Restraining yourself to a certain length can be easily done in a stop clause.

Java code:

private static void getSubsets(List<Integer> superSet, int k, int idx, Set<Integer> current,List<Set<Integer>> solution) {     //successful stop clause     if (current.size() == k) {         solution.add(new HashSet<>(current));         return;     }     //unseccessful stop clause     if (idx == superSet.size()) return;     Integer x = superSet.get(idx);     current.add(x);     //"guess" x is in the subset     getSubsets(superSet, k, idx+1, current, solution);     current.remove(x);     //"guess" x is not in the subset     getSubsets(superSet, k, idx+1, current, solution); }  public static List<Set<Integer>> getSubsets(List<Integer> superSet, int k) {     List<Set<Integer>> res = new ArrayList<>();     getSubsets(superSet, k, 0, new HashSet<Integer>(), res);     return res; } 

Invoking with:

List<Integer> superSet = new ArrayList<>(); superSet.add(1); superSet.add(2); superSet.add(3); superSet.add(4); System.out.println(getSubsets(superSet,2)); 

Will yield:

[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]] 

Answer 2

Use a bit vector representation of the set, and use an algorithm similar to what std::next_permutation does on 0000.1111 (n-k zeroes, k ones). Each permutation corresponds to a subset of size k.