递归（数学分析式子）+ long long数据类型

解题思路:
利用递归（注意一定要有递归出口 特殊情况！！①元素个数少于集合个数 没有集合 都返回0 ②集合只有一个 或者 元素个数等于集合个数 都返回1）

递归式子思路：总情况数就只有两个情况 ：①最后一个数单独一个集合 n-1个元素分成了k-1个集合 他们分法就S(n-1,k-1)的分法数；②第二种情况是n-1个元素已经分成k个集合 最后一个元素加入任意其中一个就好了(那么就有k种情况) 则该情况的分法数为k*S(n-1,k)。则总分法就是把两个情况相加

注意事项:

注意定义long long数据类型

参考代码:

#include<stdio.h>

//n为元素个数 k为集合个数

long long S(int n, int k){

    //特殊情况 元素个数少于集合个数 没有集合 都返回0

    if(n<k || k==0 || n==0){

        return 0;

    }

    //特殊情况 集合只有一个 或者 元素个数等于集合个数

    if(k==1 || n==k){

        return 1;

    }

    //总情况数就只有两个情况 

    //最后一个数单独一个集合 n-1个元素分成了k-1个集合 他们分法就S(n-1,k-1)的分法数

    //第二种情况是n-1个元素已经分成k个集合 最后一个元素加入任意其中一个就好了(那么就有k种情况) 则该情况的分法数为k*S(n-1,k)

    //则总分法就是把两个情况相加

    return S(n-1,k-1)+k*S(n-1,k);

}

int main()

{

int n,k;

scanf("%d %d",&n,&k);

long long num = S(n,k);

printf("%lld",num);

}