Recursive method to return a set of all combinations Can someone explain me how this code works or if it is possible to be written in another way? I tried it with just ArrayList but cannot figure it out.

public static Set&lt;Set&lt;Integer&gt;&gt; combinations(List&lt;Integer&gt; groupSize, int k) {

    Set&lt;Set&lt;Integer&gt;&gt; allCombos = new HashSet&lt;Set&lt;Integer&gt;&gt; ();
    // base cases for recursion
    if (k == 0) {
        // There is only one combination of size 0, the empty team.
        allCombos.add(new HashSet&lt;Integer&gt;());
        return allCombos;
    }
    if (k &gt; groupSize.size()) {
        // There can be no teams with size larger than the group size,
        // so return allCombos without putting any teams in it.
        return allCombos;
    }

    // Create a copy of the group with one item removed.
    List&lt;Integer&gt; groupWithoutX = new ArrayList&lt;Integer&gt; (groupSize);
    Integer x = groupWithoutX.remove(groupWithoutX.size()-1);

    Set&lt;Set&lt;Integer&gt;&gt; combosWithoutX = combinations(groupWithoutX, k);
    Set&lt;Set&lt;Integer&gt;&gt; combosWithX = combinations(groupWithoutX, k-1);
    for (Set&lt;Integer&gt; combo : combosWithX) {
        combo.add(x);
    }
    allCombos.addAll(combosWithoutX);
    allCombos.addAll(combosWithX);
    return allCombos;
}
Basically the algorithm returns all subsets of groupSize (which should really be renamed to group), that have k elements.

The method works recursively. To do so it needs two things : establish primitive cases that end the recursion, and a way of formulating the problem in terms of itself, yet closer to the primitive form.

This algorithm has two primitive cases : 


k == 0 : there is only one set that has 0 elements : the empty set.
k > size of the group : there are no subsets that have more elements than the original set


So there are two ways we can get to a primitive case : formulating it in terms of smaller sets (smaller group), or in terms of smaller subsets (smaller k)

The formulation in terms of itself for this algorithm is : given an element x from the group, its combinations are : all subsets that contain x, and all subsets that do not contain x.


All subsets that do not contain x, is really all subsets of the group without x of size k (moves closer to second primitive case)
All subsets that contain x, is all subsets of the group without x of size k-1 with x added to those subsets. (moves closer to both primitive cases)


The algorithm takes the last element of the group as x (but could just as well take another) : Integer x = groupWithoutX.remove(groupWithoutX.size()-1);

An example will make this clearer :

for groupSize = [1, 2, 3, 4, 5] and k = 3 the output would be 

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

Picking the last element x = 5

this is


all subsets of [1, 2, 3, 4] of size k = 3 : i.e. [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]
and all subsets of [1, 2, 3, 4] of size k = 2 and 5 added i.e. [[1, 2, 5], [1, 3, 5], [1, 4, 5], [2, 3, 5], [2, 4, 5], [3, 4, 5]]