說明
給定一組數字或符號，產生所有可能的集合（包括空集合），例如給定1 2 3，則可能的集合為：{}、{1}、{1,2}、{1,2,3}、{1,3}、{2}、{2,3}、{3}。
解法
如果不考慮字典順序，則有個簡單的方法可以產生所有的集合，思考二進位數字加法，並注意1出現的位置，如果每個位置都對應一個數字，則由1所對應的數字所產生的就是一個集合，例如：
| 000 |
{} |
| 001 |
{3} |
| 010 |
{2} |
| 011 |
{2,3} |
| 100 |
{1} |
| 101 |
{1,3} |
| 110 |
{1,2} |
| 111 |
{1,2,3} |
瞭解這個方法之後，剩下的就是如何產生二進位數？有許多方法可以使用，您可以使用unsigned型別加上&位元運算來產生，這邊則是使用陣列搜
尋，首先陣列內容全為0，找第一個1，在還沒找到之前將走訪過的內容變為0，而第一個找到的0則變為
1，如此重複直到所有的陣列元素都變為1為止，例如：
000 => 100 => 010 => 110 => 001 => 101 => 011 => 111
如果要產生字典順序，例如若有4個元素，則：
{} => {1} => {1,2} => {1,2,3} => {1,2,3,4} =>
{1,2,4} =>
{1,3} => {1,3,4} =>
{1,4} =>
{2} => {2,3} => {2,3,4} =>
{2,4} =>
{3} => {3,4} =>
{4}
簡單的說，如果有n個元素要產生可能的集合，當依序產生集合時，如果最後一個元素是n，而倒數第二個元素是m的話，例如：
{a b c d e n}
則下一個集合就是{a b c d e+1}，再依序加入後續的元素。
例如有四個元素，而當產生{1 2 3 4}集合時，則下一個集合就是{1 2 3+1}，也就是{1 2
4}，由於最後一個元素還是4，所以下一個集合就是{1 2+1}，也就是{1 3}，接下來再加入後續元素4，也就是{1 3
4}，由於又遇到元素4，所以下一個集合是{1 3+1}，也就是{1 4}。
實作
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 20
int main(void) {
char digit[MAXSIZE];
int i, j;
int n;
printf("輸入集合個數：");
scanf("%d", &n);
for(i = 0; i < n; i++)
digit[i] = '0';
printf("\n{}"); // 空集合
while(1) {
// 找第一個0，並將找到前所經過的元素變為0
for(i = 0; i < n && digit[i] == '1'; digit[i] = '0', i++);
if(i == n) // 找不到0
break;
else // 將第一個找到的0變為1
digit[i] = '1';
// 找第一個1，並記錄對應位置
for(i = 0; i < n && digit[i] == '0'; i++);
printf("\n{%d", i+1);
for(j = i + 1; j < n; j++)
if(digit[j] == '1')
printf(",%d", j + 1);
printf("}");
}
printf("\n");
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 20
int main(void) {
int set[MAXSIZE];
int i, n, position = 0;
printf("輸入集合個數：");
scanf("%d", &n);
printf("\n{}");
set[position] = 1;
while(1) {
printf("\n{%d", set[0]); // 印第一個數
for(i = 1; i <= position; i++)
printf(",%d", set[i]);
printf("}");
if(set[position] < n) { // 遞增集合個數
set[position+1] = set[position] + 1;
position++;
}
else if(position != 0) { // 如果不是第一個位置
position--; // 倒退
set[position]++; // 下一個集合尾數
}
else // 已倒退至第一個位置
break;
}
printf("\n");
return 0;
}
public class PossibleSet {
public static void main(String[] args) {
char[] digit = new char[4];
for(int i = 0; i < digit.length; i++)
digit[i] = '0';
System.out.println("{}"); // 空集合
while(true) {
// 找第一個0，並將找到前所經過的元素變為0
int i;
for(i = 0; i < digit.length && digit[i] == '1';
digit[i] = '0', i++);
if(i == digit.length) // 找不到0
break;
else // 將第一個找到的0變為1
digit[i] = '1';
// 找第一個1，並記錄對應位置
for(i = 0; i < digit.length && digit[i] == '0'; i++);
System.out.print("{" + (i+1));
for(int j = i + 1; j < digit.length; j++)
if(digit[j] == '1')
System.out.print(", " + (j + 1));
System.out.println("}");
}
}
}
public class PossibleSet {
public static void main(String[] args) {
int[] set = new int[4];
int i, n, position = 0;
set[position] = 1;
while(true) {
System.out.print("{" + set[0]); // 印第一個數
for(i = 1; i <= position; i++)
System.out.print("," + set[i]);
System.out.print("}");
if(set[position] < set.length) { // 遞增集合個數
set[position+1] = set[position] + 1;
position++;
}
else if(position != 0) { // 如果不是第一個位置
position--; // 倒退
set[position]++; // 下一個集合尾數
}
else // 已倒退至第一個位置
break;
}
System.out.println();
}
}