n个元素的集合{1，2，…，n}可以划分若干非空子集。例如，当n=4时，集合{1，2，3，4}可以划分为15个不同的非空子集如下：

{{1},{2},{3},{4}} {{1,3},{2,4}}

{{1,2},{3},{4}} {{1,4},{2,3}}

{{1,3},{2},{4}} {{1,2,3},{4}}

{{1,4},{2},{3}} {{1,2,4},{3}}

{{2,3},{1},{4}} {{1,3,4},{2}}

{{2,4},{1},{3}} {{2,3,4},{1}}

{{3,4},{1},{2}} {{1,2,3,4}}

{{1,2},{3,4}}

给定正整数n，计算出n个元素的集合{1,2,，…，n}可以划分为多少个不同的非空子集。

输出集合数目及不同的集合。

测试数据为5和6

输入

5

输出

划分为1个数组的情况有：
{{1,2,3,4,5}}
划分为2个数组的情况有：
{{1,2,3,4},{5}}
{{1,2,3,5},{4}}
{{1,2,5,4},{3}}
{{1,5,4,3},{2}}
{{1,5,4},{2,3}}
{{1,2,5},{4,3}}
{{1,5,3},{2,4}}
{{1,5},{2,4,3}}
{{1,2,3},{5,4}}
{{1,2,4},{5,3}}
{{1,4,3},{2,5}}
{{1,4},{2,5,3}}
{{1,2},{5,4,3}}
{{1,3},{2,5,4}}
{{1},{2,5,4,3}}
划分为3个数组的情况有：
{{1,2,3},{4},{5}}
{{1,2,4},{3},{5}}
{{1,4,3},{2},{5}}
{{1,4},{2,3},{5}}
{{1,2},{4,3},{5}}
{{1,3},{2,4},{5}}
{{1},{2,4,3},{5}}
{{1,2,5},{3},{4}}
{{1,5,3},{2},{4}}
{{1,5},{2,3},{4}}
{{1,5,4},{2},{3}}
{{1,5},{2,4},{3}}
{{1,5},{2},{3,4}}
{{1,2},{5,3},{4}}
{{1,3},{2,5},{4}}
{{1},{2,5,3},{4}}
{{1,4},{2,5},{3}}
{{1},{2,5,4},{3}}
{{1},{2,5},{3,4}}
{{1,2},{3},{5,4}}
{{1,3},{2},{5,4}}
{{1},{2,3},{5,4}}
{{1,4},{2},{3,5}}
{{1},{2,4},{3,5}}
{{1},{2},{3,5,4}}
划分为4个数组的情况有：
{{1,2},{3},{4},{5}}
{{1,3},{2},{4},{5}}
{{1},{2,3},{4},{5}}
{{1,4},{2},{3},{5}}
{{1},{2,4},{3},{5}}
{{1},{2},{3,4},{5}}
{{1,5},{2},{3},{4}}
{{1},{2,5},{3},{4}}
{{1},{2},{3,5},{4}}
{{1},{2},{3},{4,5}}
划分为5个数组的情况有：
{{1},{2},{3},{4},{5}}
总共有52种情况

代码

#include <iostream>
using namespace std;
int a[101][101],b[101]={0};//a里面存储集合元素，b存储集合元素个数 
int n,sum=0,M;//sum记录总数，M存储最原先要划分的集合个数 
int tongji(int c,int m)//b为数字个数，m为所划分集合个数 
{
	int i,j;
	if(m==1||c==m)//当满足条件m等于1或c和m相等时输出 
	{
		cout<<'{';//输出左边最外面的花括号 
		if(m==1)//当m为1时 
		{
			cout<<'{';//输出{
			for(i=1;i<=c;)//把1到c的所有数字当作第一组输出 
			{
				if(i!=1) cout<<',';
				cout<<i++;
			}
			for(i=0;i<b[1];)//合并数组存储的第一组的元素
			{
				cout<<',';
				cout<<a[1][i++];
			}	
			cout<<'}';//输出}
			for(j=2;j<=M;j++)//输出a数组存储的几个集合 
			{
				cout<<',';//输出逗号分隔集合
				cout<<'{';//输出{
				for(i=0;i<b[j];)
				{
					if(i!=0) cout<<',';
					cout<<a[j][i++];
				}
				cout<<'}';//输出}
			}
			
		}
		else//c==m的情况下
		{
			for(j=1;j<=M;j++)//把1-c分别作为1-c组集合的元素 
			{
				if(j!=1)  cout<<',';//输出逗号分隔集合，第一组不用 
				cout<<'{';//输出{
				if(j<=c) cout<<j;//把j作为j组集合的元素输出 
				for(i=0;i<b[j];)//输出a数组存储的几个集合
				{
					if(j<=m||i!=0) cout<<',';
					cout<<a[j][i++];
				}
				cout<<'}';//输出}
			}
		}
		cout<<'}'<<endl;//输出右边最外面的花括号，换行 
		sum++;//总数加一 
	}
	else
	{
		a[m][b[m]++]=c;
		tongji(c-1,m-1);
		b[m]--;//还原为原来的数组 
		for(i=1;i<=m;i++)//让数字c存储在第1到第m个集合，再递归 
		{
			a[i][b[i]++]=c; //让数字c存储在第i个集合
			tongji(c-1,m); //继续递归调用自身 
			b[i]--;//还原为原来的数组
		}
	}
}
int main()
{
	int n,i;
	cin>>n;//输入n 
	for(i=1;i<=n;i++)//按划分数组个数来划分种类 
	{
		cout<<"划分为"<<i<<"个数组的情况有："<<endl; 
		M=i;//用M存储最原先要划分的集合个数 
		tongji(n,i);//套用函数，划分为i个集合
	}
	cout<<"总共有"<<sum<<"种情况"<<endl;//输出总数 
}