3. (整数划分问题) 将正整数n表示成一系列的正整数之和： n=n1+n2+…+nk, 其中n1≥n2≥…≥nk≥1，k≥1，求正整数n的不同划分个数。（递归实现

整数划分问题，也称为部分和问题或分隔计数问题，是一个经典的组合数学问题。递归实现可以参考下面的思路：

假设我们有一个函数 `countParts(n, k)`，它接收两个参数：目标总和 `n` 和已分配的部分个数 `k`。这个函数的目标是计算从 `1` 到 `n` 中选择 `k` 个非降序数字的不同组合。

基本情况：
- 如果 `n == 0`，并且 `k == 0`，这意味着找到了一种空的划分方案，所以返回 `1`。
- 如果 `n < 0` 或 `k = 0`，则没有合法的划分，返回 `0`。

递归情况：
- 对于 `n > 0`，考虑当前是否需要增加一个新的最大部分 `k`。如果添加 `k`，那么剩余的和为 `n - k`，并减小部分个数到 `k - 1`。因此，这部分的解就是 `countParts(n - k, k - 1)`。
- 如果不需要增加新的最大部分，则剩下的部分个数不变，但是每个现有的部分都可以选择是否添加到划分中，所以这部分的解是 `countParts(n, k)` 乘以当前最大的 `k` 项的数目，即 `countParts(n, k) * k`。

递归公式可以写为：

countParts(n, k) = countParts(n - k, k - 1) + (k * countParts(n, k))

最后，为了得到总的划分数，你需要对所有可能的 `k` 从 `1` 到 `n` 遍历，并将结果相加：

def countDistinctPartitions(n):
    return sum(countParts(n, i) for i in range(1, n + 1))