Subsets of Size K

Generate all possible subset of size k of given array with distinct elements.

Input :   {1, 2, 3, 4}
          k = 2
Output :  1 2
          1 3
          1 4
          2 3
          2 4
          3 4

https://www.geeksforgeeks.org/print-subsets-given-size-set/

Solution & Analysis

Recursive -Backtracking

// "static void main" must be defined in a public class.
public class Main {
    private static void getSubsets(List<Integer> superSet, int k, int idx, 
            List<Integer> current, List<List<Integer>> solution) {

        if (current.size() == k) {
            solution.add(new ArrayList<>(current));
            return;
        }

        for (int i = idx; i < superSet.size(); i++) {
            Integer x = superSet.get(i);
            current.add(x);
            getSubsets(superSet, k, i + 1, current, solution);
            current.remove(current.size() - 1);
        }
    }

    public static List<List<Integer>> getSubsets(List<Integer> superSet, int k) {
        List<List<Integer>> res = new ArrayList<>();
        getSubsets(superSet, k, 0, new ArrayList<Integer>(), res);
        return res;
    }

    public static void main(String[] args) {
        int k = 3;
        List<Integer> superSet = new ArrayList<>();
        superSet.add(1);
        superSet.add(2);
        superSet.add(3);
        superSet.add(4);
        superSet.add(5);
        List<List<Integer>> res = getSubsets(superSet, k);
        System.out.println(res);
    }
}

Reference

https://stackoverflow.com/questions/12548312/find-all-subsets-of-length-k-in-an-array

Last updated