2013-05-31 71 views
-1

有人能解釋我這個代碼是如何工作的嗎?是否有可能以另一種方式寫作?我試過它只是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; 
} 
+3

試一下:http://codereview.stackexchange.com/ – SomeWittyUsername

+0

這不是遞歸。你的意思是「組合」而不是「showTeam」? –

+0

是組合!對於錯誤 – user2441143

回答

0
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. 
+0

可以不使用? – user2441143

+0

你需要某種集合。它可以是任何類型,但集合是最合乎邏輯的,因爲您不希望集合中有多個相同的元素,而且您也不關心訂單。 – LunaEques