我們知道，一個集合的子集通?？捎梢粋€位串來表示，比如對于集合 {a, b, c, d, e}，可用位串 s = ”11001” 來表示其子集 {a, b, e}。當集合的大小不大于機器的字長（在下文中將假設字長為32）時，這些位串又可用一個無符號整數來表示，比如上面的 s 可以存儲為 0b10011 = 19。在此種情形下，很多集合操作都可以通過位運算來完成，一些常見操作如下：
求集合 A, B 的交集: a & b
求集合 A, B 的并集: a | b
求集合 A 的補集：~a
求集合 A – B：a & (~b)
測試集合 A 是否包含第 i 個元素：(a & (1<<i)) != 0
測試集合 A 是否是集合 B 的父集：(a & b) == b
當然，這些操作還有很多，比如求對稱差就是一個異或等等，這里就不一一列舉了，因為這并不是本文的重點。本文的主要目的是討論一些集合上的組合搜索。具體來說就是怎樣高效遍歷一個集合的所有子集（subset），或者一個集合的含有固定元素個數的所有子集（亦即是組合，combination）。如果你對怎么實現這些操作不感興趣，你可以直接下載本文所附的代碼，里面包含了已經封裝好了的類，和一些簡單的例子。如果你感興趣，而且正巧知道一點常用位運算技巧的話，請 continue。
1. 遍歷所有子集
1.1 遍歷全集的所有子集
若全集 U 有 n 個元素，表示成位串為 1111…1（n個1），對應的無符號整數即是 2^n – 1 = (1 << n) - 1（注意當 n 等于32 時需要做一些調整，不過我想你也大概不會要遍歷到這么大一個集合的所有子集）。容易觀察到，U 的所有子集剛好與區間 [0, 2^n – 1] 內的所有整數形成一一映射，于是通過下面這段代碼即可依次訪問 U 的所有子集：
1 |
for (unsigned long i = 0; i < (1UL << n); ++i) |
這是每個程序員都應該知道的技巧。舉個例子，若全集為 {a, b, c}，那么上面這段代碼所訪問的子集及順序將如下表所示：
| 序號 |
值 |
位串 |
子集 |
| 1 |
0b000 |
000 |
Φ |
| 2 |
0b001 |
100 |
{a} |
| 3 |
0b010 |
010 |
|
| 4 |
0b011 |
110 |
{a, b} |
| 5 |
0b100 |
001 |
{c} |
| 6 |
0b101 |
101 |
{a, c} |
| 7 |
0b110 |
011 |
{b, c} |
| 8 |
0b111 |
111 |
{a, b, c} |
注意這里訪問子集的順序并不是 lexicographic order (lex)，而是另外一種與 lex 關系微妙的序，被稱為 colexicographic order (colex)。lex 是從左到右依次比較，而 colex 正好相反，實際上在 colex 中，如果將各子集反轉一下，比如將集合 {a, b, c} 寫成 {c, b, a}，你會發現，反轉之后的子集們正是按照 lex 排列的。在下表中列出了 {a, b, c} 的所有子集的 lex 序及 colex 序，為了看起來更方便，省略了集合符號，注意觀察 lex 與 colex 之間的聯系。
| lex |
colex |
| Φ |
Φ |
| a |
a |
| ab |
b |
| abc |
ba |
| ac |
c |
| b |
ca |
| bc |
cb |
| c |
cba |
再說說如何反向的遍歷所有子集。這個其實很顯然，因為 ++i 的逆操作是 --i ，因此對上面的代碼做點小修改即得到 reverse colex：
1 |
for (unsigned long i = (1UL << n) - 1; ; --i) |
1.2 遍歷子集的所有子集
有些時候我們不僅需要遍歷全集的所有子集，還需要遍歷某個子集的所有子集。你可能會想這似乎沒什么區別啊，因為當針對某個子集來討論其所有子集時，這個子集也就成了全集。的確，在數學上當我們要考慮某個集合的冪集時，并不需要區別這個集合是全集還是全集的某個子集。但是當集合是用位串來表示時，情況就發生變化了，因為正是一個約定的全集決定了位串的長度，同時也決定了位串中的每個位與全集中的哪個元素相對應，換句話說就是定義了位串與子集之間的映射關系。如果想將某個子集做為全集來處理，你就必須重新進行映射。舉個例子，若全集為 U = {a, b, c, d, e}，若想得到它的一個子集 S = {a, e} 的所有子集，可以暫時先將 S 做為一個全集來處理，按照上面遍歷全集的算法將依次得到位串 00, 10, 01, 11，這些位串的第1位代表元素 a，第2位代表元素 e。當再回到全集 U 上時，由于 U 上的位串是第1位代表 a，第5位代表 e，因此還需要進行一個映射將 S 上的位串映射為 U 上的位串。下表按照 colex 依次列出了 S 的所有子集，注意從 S 到 U 的映射關系。
| 序號 |
值 |
映射 |
位串 |
子集 |
| 1 |
0b00 |
0b00000 |
00000 |
Φ |
| 2 |
0b01 |
0b00001 |
10000 |
{a} |
| 3 |
0b10 |
0b10000 |
00001 |
{e} |
| 4 |
0b11 |
0b10001 |
10001 |
{a, e} |
一個映射操作可以重新敘述如下：給定一個 n 位的二進制數 u，一個 m 位的二進制數 v，且有在 u 中1的個數等于 m 。設在 u 中為1的位的索引從低到高依次為 p1,p2,…,pm，再設下標操作符 [] 可以索引一個二進制數的某個位（最低位的索引為1），那么映射操作將返回一個 n 位二進制數 w，滿足
對所有 1 <= i <= n ，若u[i] = 0，則 w[i] = 0
對所有 1 <= i <= m ，w[pi] = v[i]
比如給定 u = 0b10110100, v = 0b1100, 將得到 w = 0b10100000。這個映射操作是 non-trival 的，也就是說你不能指望通過簡單的一兩次位運算就能得償所愿。具體怎么實現咱們后面再講，因為在這里使用一個非常漂亮的技巧可以繞過這個操作。為了敘述方便，先定義一個概念（非正式）：
片段：對于任意兩個 n 位二進制數 x 和 mask，若在 mask 中為1的位的索引分別為 p1,p2,…,pk，那么將這些位 x[p1],x[p2],…,x[pk] 稱為 x 在 mask 上的片段，不妨記為 [x@mask]。比如對于 x = 0b0001, mask = 0b1001, 那么 [x@mask] 由 x 的第1位和第4位組成，用紅色標識出來即為 0b0001。
在前面我們已經看到，遍歷子集的關鍵就是一個+1（colex）或者-1（reverse colex）操作。如果我們能在片段上直接進行+1或者-1操作，那就解決問題了。比如 0b0001 + 1 直接就得到 0b1000。事實上，這的確可以做到，而且非常簡單。
先來看看片段上的-1操作（因為-1比+1簡單，而且也有更多的人知道這一技巧）。若 x & mask = x，即 x 是 mask 的子集，則有：
[x@mask] - 1 = (x – 1) & mask
上面這個公式為什么是正確的？因為既然 x 是 mask 的子集，因此 mask 為0的位在 x 中也為0。這些0在-1運算中會正確的傳播借位，就如同它們并不存在一樣。比如 0b1000 – 1 = 0b0111（注意在第1位中產生的借位是如何傳播到第4位的）。最后再與 mask 相與，清零掉那些無關的位，即得到正確的結果 0b0001。
于是，如果想要按照 reverse colex 遍歷某個子集（假設表示成一個無符號整數為 s) 的所有子集，將 s 做為 mask 然后進行-1操作即可，代碼如下：
1 |
for (unsigned long i = s; ; i = (i - 1) & s) |
再來看看如何在片段上進行+1操作。受上面-1操作的啟發，我們意識到這里最關鍵的問題在于如何正確的傳播進位。傳播借位是將無關位設為0，那傳播進位呢？——將無關位設為1，Bingo!。怎么將無關位設為1呢，將mask取反，然后再相或就成，于是有：
[x@mask] + 1
= ((x | (~mask)) + 1) & mask
= (x + (~mask) + 1) & mask // 若 x & mask = x，那么 x | (~mask) = x + (~mask)
= (x – mask) & mask // (~mask) + 1 = – mask
現在我們終于可以正向地遍歷子集 s 的所有子集了：
1 |
for (unsigned long i = 0; ; i = (i - s) & s) |