Generating subsets of a set

學習筆記 of Competitive Programming's Handbook by Antti Laaksonen (5.1)

枚舉出所有子集合的方法有二：
1. 使用遞迴(recursion)：
    每個元素都分為「取」跟「不取」
2. 利用二進位整數的位元：
    「1」逐步左移(<<)，進行&位元運算

＊遞迴的概念比較複雜，假設集合內有{1, 2, 3}，我們預設一個subset是空集合，先從1開始，1可以取或不取，先討論不取的情況，再看2，2也有取與不取，3也有。

所以第一個情況應該是：1不取、2不取、3不取
三個元素都討論過後，就印出該子集（此情況為空集合{}）

接下來我們取3，2不取、1不取，印出{3}
會先取3的原因是，呼叫3的函式第一個返回接續
再來3會被pop掉，因為3是最後一個元素

接著返回呼叫2的函式
取2，1、3不取，印出{2}
注意，再來2還不會pop掉，因為2是第二個元素，後面還有3
所以接下來是取2取3，1不取，印出{2, 3}
pop 3、pop 2

照著相同的模式，接下來會是：
{1}
{1, 3}
{1, 2}
{1, 2, 3}
總共八組(2^3)
（PS. 取1的情況，可以觀察到後面2跟3的選取方式跟上面一模一樣，因為是遞迴嘛！）
如果覺得描述很抽象，可以對照著程式碼畫出樹狀圖，一步一步觀察


＊第二個方法也很有趣，我們可以先看二進位中 0 到 111 的數字：
000、001、010、011、100、101、110、111
每一個位元視為一個元素，1為取，0為不取，這八個數字就代表所有子集了！
{}、{1}、{2}、{1, 2}、{3}、{1, 3}、{2, 3}、{1, 2, 3}

實作的方法：用位元AND(&)判斷該位元為1或為0，以及用左移運算子(<<)逐步比較所有位元

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

＊程式碼以C++為例：

#include <iostream>
#include <vector>
#include <set>
#include <cmath>
using namespace std;

vector<int> subsets; //m1's subsets 的 index

void m1(int k, vector<int> s){
    int n = (int)s.size();
    
    if (k == n) { //印出子集
        cout << "{";
        bool f = false;
        for (auto it : subsets) {
            if (f) cout << ",";
            f = true;
            cout << s[it];
        }
        cout << "}" << endl;
    }
    
    else { //key point!
        m1(k+1, s); //不取
        subsets.push_back(k);
        m1(k+1, s); //取
        subsets.pop_back();
    }
}

void m2(vector<int> s){
    int n = (int)s.size();
    
    for (int i = 0; i < (1<<n) ; i++) { //key point!
        cout << "{";
        bool f = false;
        for (int j = 0; j < n; j++) {
            if (i & (1<<j)) { //key point! 1左移
                if (f) cout << ",";
                f = true;
                cout << s[j];
            }
        }
        cout << "}" << endl;
    }
}

int main(int argc, const char * argv[]) {
    vector<int> s = {0, 5, 7};
    m1(0, s);
    cout << "=========" << endl;
    m2(s);
    return 0;
}