2.6.3  从n个事物中选出k个

某支摇滚乐队希望在n个城市巡回演出。遗憾的是，由于时间原因只能访问k个城市。乐队经纪人考虑从n个可能的城市选择k个城市的不同选择。由于时间紧迫，乐队成员不考虑访问k个城市的顺序。

令g(n,k)为从n个城市选择k个城市的方案数目。考虑城市C，那么只有访问与不访问两种选择。如果访问城市C，那么就需要从n-1个剩余的城市中选择k-1个城市。因此，包含城市C的方案数目为g(n-1, k-1)。相反，如果不访问城市C，就必须从剩余的n-1个城市中选择k个城市。不包含C的方案数目为g(n-1, k)。因此，可以将g(n,k)分解为相同类型的两个较小的问题，也就是说：

g(n, k) = g(n-1, k-1) + g(n-1, k)

注释：从n个事物中选择k个的方案数目等于从n-1个事物中选择k-1个的方案数目加上从n-1个事物中选择k个的方案数目

我们仍然需要找到基例，并说明这两个较小的问题最终都能够到达基例。首先，如果乐队有时间到达全部n个城市，也就是说k等于n，那么方案只有一种。因此，第一个基例为：

g(k, k) = 1

如果k<n，则递归定义中的第二项g(n-1,k)可以到达这个基例，因为在连续的递归过程中，n-1持续下降到k。然而，第一项g(n-1, k-1)不会到达这个基例。由于n-1与k-1以同样的速率下降，因此永远不会相等。实际上，第一项是另一个旅程选择问题。就像访问所有城市只有一个选择(k=n)那样，访问0个城市也只有一个选择(k=0)。因此，第二个基例是：

g(n, 0)=1

第一项g(n-1, k-1)最终将到达这个基例(此外，也可以将第二个基例定义为g(n,1)=n)。

提示：当通过解决两个(或者多个)较小问题来解决某个问题时，每个较小问题必须比原始问题更靠近基例。

为了完整性，将最后一部分添加到递归解决方案中：

g(n, k) = 0    若k >n

尽管在本问题中，k不会大于n；但是这部分内容的加入可使该递归解决方案更加通用。

总而言之，下面的递归解决方案可以解决从n个事物中选择k个的问题：
 

注释：从n个事物中递归选择k个事物的方案数目

根据这个递归定义，不难得出下面的函数：
 

/** Computes the number of groups of k out of n things.  
@pre  n and k are nonnegative integers.  
@post  None.  
@param n  The given number of things.  
@param k  The given number to choose.  
@return  g(n, k). */  
int getNumberOfGroups(int n, int k)  
{  
if ( (k == 0) || (k == n) )  
return 1;  
else if (k > n)  
return  0;  
else  
return getNumberOfGroups(n - 1, k - 1) + getNumberOfGroups(n - 1, k);  
} // end getNumberOfGroups 

与rabbit函数类似，该函数的效率不高且不实用。图2-20显示计算g(4, 2)时需要的递归调用数目。

提示：当递归函数包含多个递归调用时，通常需要多个基例。

问题10 计算g(4, 2)。