c++ - 计算将具有 n 个元素的集合分成 k 个子集的分区数

Question

这个程序用于计算将具有 n 个元素的集合划分为 k 个子集的数量我在这里感到困惑 return k*countP(n-1, k) + countP(n-1, k-1); 有人可以解释这里发生了什么吗？ 为什么我们要乘以 k？

注意->我知道这不是计算 DP 分区数的最佳方法

// A C++ program to count number of partitions 
// of a set with n elements into k subsets 
#include<iostream> 
using namespace std; 

// Returns count of different partitions of n 
// elements in k subsets 
int countP(int n, int k) 
{ 
    // Base cases 
    if (n == 0 || k == 0 || k > n) 
        return 0; 
    if (k == 1 || k == n) 
        return 1; 

    // S(n+1, k) = k*S(n, k) + S(n, k-1) 
    return k*countP(n-1, k) + countP(n-1, k-1); 
} 

// Driver program 
int main() 
{ 
    cout << countP(3, 2); 
    return 0; 
} 

Answer 1

每个 countP 调用隐含地考虑集合中的单个元素，我们称它为 A。

countP(n-1, k-1) 术语来自于 A 单独在一个集合中的情况。在这种情况下，我们只需要计算将所有其他元素 (N-1) 划分为 (K-1) 个子集的方法有多少，因为 A 本身占据了一个子集。

然后，k*countP(n-1, k) 项来自 A 不 在集合中的情况通过它自己。因此，我们计算出将所有其他 (N-1) 个值划分为 K 个子集的方法数，并乘以 K，因为有 K 个可能的子集我们可以添加 A。

例如，考虑集合 [A,B,C,D]，K=2。

第一种情况，countP(n-1, k-1)，描述了以下情况:

{A, BCD}

第二种情况，k*countP(n-1, k)，描述了以下情况:

2*({BC,D}, {BD,C}, {B,CD}) 

或者:

{ABC,D}, {ABD,C}, {AB,CD}, {BC,AD}, {BD,AC}, {B,ACD}