Рекурсивный метод для возврата набора всех комбинаций

Question

Может ли кто-нибудь объяснить мне, как работает этот код? Можно ли писать по-другому? Я попробовал это только с ArrayList, но не могу понять.

public static Set<Set<Integer>> combinations(List<Integer> groupSize, int k) { 
    Set<Set<Integer>> allCombos = new HashSet<Set<Integer>>(); 

    // base cases for recursion 
    if (k == 0) { 
     // There is only one combination of size 0, the empty team. 
     allCombos.add(new HashSet<Integer>()); 
     return allCombos; 
    } 
    if (k > 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<Integer> groupWithoutX = new ArrayList<Integer> (groupSize); 
    Integer x = groupWithoutX.remove(groupWithoutX.size()-1); 

    Set<Set<Integer>> combosWithoutX = combinations(groupWithoutX, k); 
    Set<Set<Integer>> combosWithX = combinations(groupWithoutX, k-1); 
    for (Set<Integer> combo : combosWithX) { 
     combo.add(x); 
    } 
    allCombos.addAll(combosWithoutX); 
    allCombos.addAll(combosWithX); 
    return allCombos; 
} 

Answer 1

The code returns a set of integer sets with all possible combinations of the integers in the first given set with k integers. I'll just demonstrate what it does with the case with list = [1,2,3] and k = 2. 

groupWithoutX = [1,2]. 
x = 1. 
k = 2. 

Then, in the call combinations(groupWithoutX, k), the second base case is true, so the method just returns [1,2]. 


In the other recursive call, the recursion happens again. 

groupWithoutX = [1]. 
x = 2. 
k = 1. 

The first call returns 1. 
The second call returns an empty set. 
However, x must be added to this empty set, so it becomes 2. 

The second recursive call of the initial call of the method, then, returns a set of the sets of integers: [1] [2] 

Back at the first call of the method, x = 3 must be added to each of the sets the second recursive call. [1] becomes [1,3] and [2] becomes [2,3]. 

The method returns all three created sets: [1,2] [1,3] [2,3]. 

In other words, this method is similar to the combination (nCr) in math, except it returns the sets created rather than just the number of sets.