fen(n)與fen(n-1)之間沒有直接函數關系，所以要寫出遞歸算法很勉強，直接給C++的非遞歸代碼
#include?<iostream>#include?<vector>
using?namespace?std;
//?將長度為n的集合劃分成非空子集，返回劃分方法的數目。
long?long?fen(int?n)
{
vector<long?long>?v(n,?0);
v[0]?=?1;
for(int?i=1;?i<=n-1;?++i)
for(int?j=i;?j>0;?--j)
v[j]?=?v[j]?*?(j+1)?+?v[j-1];
long?long?sum?=?0;
for(int?i=0;?i<n;?i++)
sum?+=?v[i];
return?sum;
}
int?main()
{
int?n;
while(cin>>n)
cout<<fen(n)<<endl;
return?0;
}
補充壹點思路，關於fen(n)與fen(n-1)的遞推關系，有點羅嗦哦。
實際上要將fen(n)按照劃分出來的非空子集的個數分成n種情況，比如將fen(4)的15種分成：含1個非空子集1種，含2個非空子集7種，含3個非空子集6種，含4個非空子集1種，15=1+7+6+1。
有5個元素的集合相比4個元素的集合，相當於在原來基礎上增加1個新元素，於是對有5個元素的集合的劃分時，有兩種做法：
a、將新元素作為單獨的壹個子集，放在原來4元素劃分的子集之外，比如{{1,2},{3,4}}變成{{1,2},{3,4},{5}}，結果非空子集的個數增加1，此類方案數目不變；
b、將新元素與其中壹個子集合並，比如{{1,2},{3,4}}變成{{1,2,5},{3,4}}，結果非空子集個數不變，因為新元素可合並到任何壹個非空子集，此類方案數目倍增，倍數取決於非空子集的個數。比如fen(4)中含3個非空子集6種方案倍增為6x3=18種。
綜合a和b的結果，fen(n)中的含k個非空子集的方案的數目有兩部分來源，壹部分是 fen(n-1)中含k個非空子集的方案，另壹部分是 fen(n-1)中含k-1個非空子集的方案數目。比如fen(5)中含3個非空子集的方案數目是 6x3+7=25。
fen(5)=(1x1+0)+(7x2+1)+(6x3+7)+(1x4+6)+(0x5+1)=52。其他以此類推。
運行結果：
從上圖可以看出，當n=16時，計算結果已經超出int表示範圍。