计算具有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调用隐含认为在设置一个单一的元素，让我们把它叫做一个。

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

因此k*countP(n-1, k)，该术语来自于A本身不在集合中的情况。因此，我们找出的所有分区的其他（N-1）值成K个子集的方式，并乘以个数K，因为有K可能的子集，我们可以添加一个到。

例如，考虑集合[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}