java - Programming a recursive method to calculate number of groups with n elements and k groups -

precondition: 0 < k <= n method needs return number of ways k groups can formed out of n distinct items. example, there 3 ways form 2 groups out of 3 items: 1. (a) (b,c) 2. (b) (a,c) 3. (c) (a,b)
, there 6 ways 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 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 know go recursive on this. see no way break down smaller subproblems because once start counting possibilities twice. appreciated.

you write:

i see no way break down smaller subproblems because once start counting possibilities twice.

this not true. once create first group, items in first group no longer in set of candidate items, , subproblem becomes counting possible groupings of remaining items - which, no coincidence, same original problem (count possible groupings of set of items).

so, then, problem boils down having count possible permutations of items in single group (e.g. a, ab, ac, bc, abc), each of those, proceeding remaining items.

once able determine number of permutations single group n available objects, end result number plus, each of permutations, number of permutations group doesn't include grouped items (n minus group size). , on, until reach base case, number of groupings of 0 items 0.

if can determine how find number of permutations of n objects (where permutations don't have include every object), you've got solved already.