2

前提条件：0 < k <= n 您的方法需要返回可以从 n 个不同项目中形成 k 个组的方式数。例如，有 3 种方法可以从 3 个项目中形成 2 个组： 1. (a) (b,c) 2. (b) (a,c) 3. (c) (a,b)
有 6从 4 个项目中形成 3 个组的方法： 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)

到目前为止我有

    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);
}

我什至不知道在哪里进行递归。我认为没有办法将其分解为更小的子问题，因为一旦你这样做了，你就会开始计算可能性两次。任何帮助将非常感激。

4

1 回答 1

0

你写：

我认为没有办法将其分解为更小的子问题，因为一旦你这样做了，你就会开始计算可能性两次。

这不是真的。创建第一组后，第一组中的项目不再在候选项目集中，子问题变为计算剩余项目的所有可能分组 - 这绝非巧合，与原始问题相同（计算一组项目的所有可能分组）。

因此，您的问题归结为必须计算单个组中项目的所有可能排列（例如 a、ab、ac、bc、abc），然后对于其中的每一个，对剩余的项目进行类似的处理。

一旦您能够确定具有 N 个可用对象的单个组的排列数，最终结果是该数字加上，对于这些排列中的每一个，不包括已分组项目的组的排列数（ N 减去组大小）。依此类推，直到达到基本情况，即 0 项的分组数为 0。

如果您可以确定如何找到 N 个对象的排列数（其中排列不必包括每个对象），那么您已经解决了这个问题。

于 2013-08-08T00:28:05.057 回答