Programming a recursive method to calculate number of groups with n
elements and k groups
Precondition: 0 < k <= n Your method needs to return the number of ways k
groups can be formed out of n distinct items. For example, there are 3
ways to form 2 groups out of 3 items: 1. (a) (b,c) 2. (b) (a,c) 3. (c)
(a,b)
and there are 6 ways to form 3 groups out of 4 items: 1. (a) (b,c) (d) 2.
(a) (b) (c,d) 3. (a) (c) (b,d) 4. (a,b) (c) (d) 5. (b) (a,c) (d) 6. (b)
(c) (a,d)
So far I have
public static int groups (int n, int k){
if(n==k){
return n;
}else if(n>1 && k==1){
return 1;
}else return n*groups(n-1, k-1);
}
I don't even know where to go for recursive on this. I see no way to break
it down into smaller subproblems because once you do you start counting
possibilities twice. Any help would be much appreciated.
No comments:
Post a Comment