先數，再算
前一篇給了你生成並測試作為最誠實的基準線：產生每個候選、逐一檢查、留下好的。但基準線只有在你知道它的代價時才有用，而把所有可能都試一遍的代價，由一個數字主宰——候選有幾個。所有候選構成的集合就是搜尋空間，而整個這一級階梯裡最重要的習慣，就是在你寫下任何一行程式之前，先估出它的大小。一個顯然正確的方法，仍可能顯然毫無希望，而搜尋空間的大小正是告訴你是哪一種的東西。
要養成的反射是這樣。當你讀一道題目時，問：「一個候選長什麼形狀？」它是對 n 個項目各做一次是非選擇嗎？是 n 個東西的某種排序嗎？還是從 n 個裡挑 k 個的某種方式嗎？每一種形狀都有已知的數量，而那個數量——寫成輸入規模 n 的函數——就是暴力法的執行時間（再乘上每個候選的測試成本）。因此數候選不是旁邊的小計算，它就是分析本身。這一級裡其他所有東西，都是讓你不必拜訪全部候選的技巧。
三種經典形狀與它們的大小
大多數暴力法問題穿著三種戲服之一。第一是子集：對 n 個項目中的每一個，你做一個獨立的「選或不選」決定，所以列舉所有子集就是走過 2 乘 2 乘 ... 乘 2，也就是 2^n 種可能（含空集合與全集）。最乾淨的想像方式是一個長度為 n 的二進位字串，每個項目一個位元：每個這樣的字串恰好命名一個子集，而這樣的字串有 2^n 個。子集和、決定要打包哪些物品、把開關打開或關掉——這些全都是 2^n 這套戲服。
第二套戲服是排序，也叫排列或安排。列舉 n 個相異東西的所有排列會得到 n! 個，因為第一個位置有 n 種選擇，第二個有 n-1 種，接著 n-2，一路往下：n 乘 (n-1) 乘 ... 乘 1。讓推銷員走過 n 座城市、安排 n 位賓客的座位、把 n 件工作排成某種順序——這些是 n! 這套戲服。第三套是不計順序地從 n 中挑 k 個，也就是組合，數量是「n 取 k」= n! / (k! (n-k)!)；從 n 人中選出 k 人的委員會、或要刪掉哪 k 條邊，都住在這裡。
shape count n=10 n=20 n=60 -------------------------------------------------------------- subsets 2^n 1,024 ~1.0 million ~1.2e18 permutations n! ~3.6 mil ~2.4e18 ~8.3e81 combos n/2 n choose n/2 252 184,756 ~1.2e17
為什麼 2^n 與 n! 是不同種類的絕望
人們很想把 2^n 和 n! 一起歸成「太大了」，但它們以非常不同的速度崩潰，而看清這個差距能磨利你的判斷。兩者都屬於成長階層裡指數的那一側——兩者最終都會輾壓任何多項式，如 n^2 或 n^100——但 n! 在過了一個極小的起點之後，對每個 n 都比 2^n 成長得更快。一個能讓你親身感受的方式：n 每增加一，2^n 就乘上固定的因子 2，而 n! 卻乘上 n，一個不斷變大的因子。所以兩者之間的差距本身就在無上限地擴大。
史特靈近似讓它變精確：n! 大約是 (n/e)^n 再乘上一個緩慢成長的尾項，所以取對數後，log(n!) 約為 n log n，而 log(2^n) 只是 n。指數裡多出來的那個 log n 因子，就是整個故事。實務上這意味著：一個列舉子集的演算法，有時還能靠更好的機器或更聰明的常數獲救；而一個列舉排列的演算法幾乎永遠不行，因為那道牆在 n 約 12 時就到了。知道你面對的是哪一種指數，就能告訴你優化到底值不值得嘗試。
一步步估算一道真實問題
讓我們來估算一道你在這一級會再遇到的具體問題的搜尋空間：在 n×n 的棋盤上放 n 個互不攻擊的皇后，也就是n 皇后問題。重點是要看出：天真的數法與聰明一點的數法，可以差了一整個星系——而且這還是在任何回溯剪掉哪怕一條分支之前。訣竅永遠相同：先釘死候選到底是什麼，再把選擇相乘。
- 最天真：一個候選是把 n 個皇后放在 n^2 個方格中的任意擺法，從 n^2 格裡選 n 格。那是「n^2 取 n」。對 8×8 的棋盤就是「64 取 8」，約 44 億個候選——已經很痛了。
- 一個觀察就讓它大幅縮小：每一行（column）至多放一個皇后。於是一個候選是替 n 個直行各選一個列（row，1..n）——每行 n 種選擇、共 n 行，得到 n^n。對 n = 8 就是 8^8，約 1670 萬。光是把候選編碼得更好，我們就把數十億砍到了數百萬。
- 第二個觀察：任兩個皇后也不能同列，所以列的指派必須是 1..n 的一個排列。現在數量是 n!，對 n = 8 只有 40,320——比 n^n 的數法低了三個數量級，比最天真的低了五個。
- 我們還沒跑任何演算法——我們只是改變了描述候選的方式。教訓是：搜尋空間不是被問題本身固定的，而是被你的表示法固定的，而更聰明的表示法是最便宜的加速。
而我們甚至還沒剪枝。回溯法——下一篇的主題——會在兩個皇后互相威脅的那一刻，就拒絕繼續延伸某個部分擺法，砍掉那 n! 空間裡整棵整棵的子樹。但請注意想法的先後次序：你先把候選編碼好，讓空間縮到誠實計數所允許的最小；然後才剪掉剩下的。估算大小要擺在最前面，因為它告訴你剪枝有沒有可能足夠。
當空間太大時：把它劈成兩半
有時候搜尋空間真的就是 2^n，而剪枝幫不上忙，因為每個候選確實都必須被考慮——例如，當數字是任意的時候，數有多少個由 n 個數字構成的子集加總等於某個目標值。這裡有個美妙的想法，現在先預告、在這一級的結尾再細講，它來自把計數的算術劈成兩半，而非把搜尋本身劈半：中間相遇法。把 n 個項目分成兩個各 n/2 大小的半邊，分別列舉每一半，再合併。
算術正是重點。兩個各 n/2 大小的半邊，各自只有 2^(n/2) 個子集，所以你生成 2 乘 2^(n/2) 個候選，而不是 2^n。由於 2^(n/2) 是 2^n 的平方根，你就把譬如 2^40（一兆，毫無希望）變成了每半邊約 2^20（一百萬，輕鬆）。代價是記憶體——你必須把一半的結果存起來，好拿去和另一半比對——以及一個用來比對的排序或雜湊步驟。它沒有打敗指數，但它把指數減半，而那往往就是可行與不可行之間的差別。
退一步，把這一整級看成對一個問題的回應：搜尋空間有某個大小，那然後呢？如果它小，就把它整個列舉出來，放輕鬆——清晰勝過聰明。如果它大但有結構，就回溯以跳過死路分支，並用定界來跳過毫無希望的分支。如果它大、沒結構、但可切分，就用中間相遇法取它的平方根。在每一種情況裡，第一步都是這篇講的同一件事：數候選，因為你無法馴服一個你連大小都還沒量過的空間。