描述
设S是一个具有n个元素的集合，S＝?a1，a2，……，an?，现将S划分成k个满足下列条件的子集合S1，S2，……，Sk，且满足：
1．Si≠∅
2．Si∩Sj＝∅(1≤i，j≤k，i≠j)
3．S1∪S2∪S3∪…∪Sk＝S
则称S1，S2，……，Sk是集合S的一个划分。它相当于把S集合中的n个元素a1，a2，……，an放入k个(0＜k≤n＜30)无标号的盒子中，使得没有一个盒子为空。请你确定n个元素a1，a2，……，an放入k个无标号盒子中去的划分数S(n,k)。
输入
给出n和k。
输出
n个元素a1，a2，……，an放入k个无标号盒子中去的划分数S(n,k)。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 7 typedef long long ll; 8 int n,k; 9 10 ll dfs(int n,int k){ 11 if(n==k||k==1) return 1; 12 if(n<k) return 0; 13 return dfs(n-1,k-1)+k*dfs(n-1,k); 14 } 15 16 int main(){ 17 ios::sync_with_stdio(false); 18 cin>>n>>k; 19 cout << dfs(n,k) << endl; 20 return 0; 21 }
样例输入
样例输出
提示
结果保证在64位整型之内
解题思路： dfs 划分为小问题来考虑 找到递归结束的条件 递推的公式 1个球要么单独放要么和他们放在一起
原文：https://www.cnblogs.com/qq-1585047819/p/11357361.html
