經典50題之第8題

輸入一變數N , 再輸入N 個數字成為一個含有N 個數的 集合A , 然後輸出所有這個A 集合的子集合。
Ex: N=3, A { 1, 2, 3 }
ANS: { 1 } { 2 } { 3 } { 1, 2 } { 1, 3 } { 2, 3 } { 1, 2, 3 } { } <--- 空集合

解法：
首先先畫如下的表格
abcd
0000 -> { }

1000->{a}
0100->{b}
0010->{c}
0001->{d}

1100->{a,b}
1010->{a,c}
1001->{a,d}
0110->{b,c}
0101->{b,d}
0011->{c,d}

1110->{a,b,c}
1101->{a,b,d}
1011->{a,c,d}
0111->{b,c,d}

1111->{a,b,c,d}

你可以將abc看成是一個二進位的字串，1代表有該元素、0代表無該元素
而abc的長度是3，所以二進位的字串長度也是3，從000~111

000代表{}
100代表有第一個元素，所以是{a}
010代表有第二個元素，所以是{b}
001代表有第三個元素，所以是{c}

101代表有第一、三個元素，所以是{a,c}
110代表有第一、二個元素，所以是{a,b}
011代表有第二、三個元素，所以是{b,c}
111代表有第一、二、三元素，所以是{a,b,c}

看出來了嗎？
長度為3的二進位，共有2^3=8種可能
剛好可以表示成你要的狀況，所以你只要將
1. 長度為3的二進位算出來
2. 再將字串裡有1的元素組合出來
就是結果了