本节通过解决集合划分的问题进行一个递归算法的简单实现.
问题描述:
给定正整数n和m,计算出n个元素的集合{1,2,3....}可以划分为多少个不同的有m个非空子集组成的集合.
思路解析:
解读题目,将由n个元素组成的集合拆分成m个非空子集,假设函数名为f.若想将n个元素分成m组,就需要考虑第n个元素要放在什么位置,剩余元素需要被放在多少个分组中.
第n个元素有两种选择:一是将第n个元素单独成一组,则剩余n-1个元素应当被分在m-1个组中,执行递归调用f(n-1,m-1);二是将第n个元素放到m个已经分好的组中的一组里,在m组中选择一个组有m中方式,则剩余n-1个元素应当被分在m组中,,执行递归调用mf(n-1,m).递归终止条件为当元素总数与分组数相等时,只有一种分组形式.变量如下:
n变量:表示元素总数
m变量:表示分成的非空集合的数目
完整代码如下:
class Solution():def setcount(self, n, m):# 如果 m 为 1 或 n 等于 m，返回 1# 这是因为从 n 个元素中选择 1 个元素或选择所有 n 个元素都只有一种方式if m == 1 or n == m:return 1else:# 否则，递归计算组合数# C(n, m) = C(n-1, m-1) + C(n-1, m) * m# 这里使用了组合数的递归性质return self.setcount(n-1, m-1) + self.setcount(n-1, m) * m