求集合的子集、全排列總結

一、輸出n個元素的集合所有的子集，如{a,b,c}的子集就有{}，{a}，{b}，{c}，{a,b}，{a,c}，{b,c}，{a,b,c}。

方法1：利用2進制表示

/*
對于集合{A,B,C,D}，它的非空子集個數為2×2×2×2－1，用二進制表示就是1111，我們規定從左到右第1位對應A，
第2位對應B，第3位對應C，第4位對應D。如果相應位為1，則表示存在該字元，否則不存在該字元。如1101就表示{A，B，D}。
這樣，對于一個n個字元組成的集合，根據n可以算法它的非空子集個數為m（2的n次幂－1），将m轉換為二進制數，然後采用每次減1的方法，即可得到所有子集。
*/ 
void SubSets(const char* str)
{
	int len = strlen(str);
	
	for(int i = 0; i < (1<<len); i++) //2^len 個子集 
	{
		cout<<"{ ";
		
		//判斷數i的二進制中第1<<j位是否為1 
		for(int j = 0; j < len; j++)  
		{
			if( (i&(1<<j) ) != 0)
			{
				cout<<str[j];
			}
		}
		cout<<" }"<<endl;
	}
}
           

int main()
           

{
	const char *str = "abc";
	
	SubSets(str);
	
	system("pause");
}
           

方法2 ：遞歸
           

void SubSets(const char* str, char out[], int curr, int start)
{
	int n = strlen(str);
	
	for(int i = start; i < n; i++)
	{
		out[curr] = str[i];
		out[curr+1] = '\0';
		
		printf("%s\n", out);
		
		if(i < n-1)
			SubSets(str, out, curr+1, i+1); 
	}
}
int main()
{
	const char *str = "abc";
	char *out = new char[strlen(str) + 1];
	memset(out, 0, strlen(str)+1);
	
	SubSets(str, out, 0, 0);
	
	system("pause");
}