集合划分问题

n个元素的集合可以划分为若干非空子集。例如，当n=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}} {{1}{2,3,4}} {{3,4}{1}{2}} {{1,2}{3,4}} {{1,2,3,4}} 要求：给定n个元素，计算它可以划分为多少个不同的非空子集？ 样例输入： 5  样例输出： 52 #include<stdio.h> int s(int n,int m) { if(m == 1 || m == n) return 1; if(m > n) return 0; return m * s(n - 1,m) + s(n - 1,m - 1);//m * s(n - 1,m)表示n - 1个数分成m个集合的可能数，这种情况总共有m种情况，也就是说不用的那个数有m种情况 //s(n - 1,m - 1)表示n - 1个数分成m - 1个集合，剩下的那个数正好作为一个集合 } int f(int n) { int count = 0; int i; for(i = 1;i <= n;i ++) count = count + s(n,i); return count; } int main() { int n = 4,m = 3; printf("%d\n",s(n,m)); printf("%d\n",f(n)); return 0; }