# 前言

排列組合如何把所有的組合都列出來可以用窮舉的方式來完成，最經典的問題就是八皇后問題。窮舉的時間複雜度很糟糕，一般寫程式會盡量避免寫出純粹窮舉的程式，會盡量利用一些演算法來提高程式的執行效率，不過用來 Debug 或是測試一些東西窮舉也是相當好用的概念，同時也是演算法的基礎。

這一章除了沿用我原本的窮舉／回溯內容，也補上 2023 CISCON《枚舉》課程（Fishhh）裡對「暴力」的分類方式，以及剪枝、位元枚舉、折半枚舉的觀念。

# 窮舉是「聰明的暴力」

何謂枚舉？就是暴力硬幹。但往往暴力不能解決事情，所以我們要有「聰明的暴力」。在許多比賽中（IOI 制），往往都會有幾個 case 是可以透過枚舉可以算出來的，學會枚舉可以幫你更好的撈分。

# 例題：找因數組合

給你 t (1 ≤ t ≤ 10^6) 個正整數 x (1 ≤ x ≤ 10^6)，請你找到共有幾組非負整數 a,b 滿足 a×b=x 。

這題有許多解法，以下提供幾個可能的複雜度： O(tx^2) 、 O(tx) 、 O(t log x) 。

最直觀的想法：開兩個 for 迴圈枚舉 a、b， O(x^2) ，燒雞 TLE 了。

優化一次：觀察到，如果我們知道 a，那麼 b 就是 x/a ，所以只要用一個 for 迴圈枚舉 a 就可以了，複雜度變成 O(x) 。

再優化一次：觀察到這就是在算 x 的因數個數，那要怎麼算 x 的因素個數呢？答案是質因數分解。可以用 O(√x) 建立質因數表，然後用 O(log x) 的時間來算出 x 的公因數數量，最後一樣用 O(log x) 的時間把答案算出來即可。

// [來源：本文補充，待替換]

// 先用 O (sqrt (MAX_X) log log MAX_X) 篩出最小質因數表

int minPrime[N];

void sieve(int n){

    for (int i = 2; i <= n; i++){

        if (minPrime[i]) continue;

        for (int j = i; j <= n; j += i)

            if (!minPrime[j]) minPrime[j] = i;

    }

}

// 質因數分解 x，回傳每個質因數的次方數乘積計算因數個數 O (log x)

int countDivisors(int x){

    int result = 1;

    while (x > 1){

        int p = minPrime[x], cnt = 0;

        while (x % p == 0){ x /= p; cnt++; }

        result *= (cnt + 1);

    }

    return result;

}

這個例子展示了枚舉的核心心法：先寫出最暴力的版本，再一層一層觀察哪裡有多餘的重複，逐步優化。從 O(x^2) 到 O(x) 到 O(log x) ，每一步都是同一個問題，只是看得更深入。

# 判斷枚舉範圍不一定像想的那麼大：調和級數的技巧

有一類題目表面上看起來是 O(n^2) ，但實際枚舉的次數遠小於此，原因是調和級數（harmonic series）： 1 + 1/2 + 1/3 + ... + 1/n ≈ ln(n) 。

# 例題：Pleasant Pairs

給一組長度為 n (2 ≤ n ≤ 10^5) 的序列 a，元素 a_i 滿足 1 ≤ a_i ≤ 2n，且序列中每個元素都不重複出現，請你找到有幾組 (i,j)(1 ≤ i < j ≤ n) 滿足 a_i × a_j = i + j 。

直覺上似乎要枚舉所有 (i,j) pair，是 O(n^2) 。但關鍵的觀察藏在題目條件裡：因為 i + j < 2n ，所以對於每個 a_i ，只會有 2n / a_i 個 a_j 滿足 a_i × a_j ≤ 2n （其餘的乘積一定超標，不可能滿足）。

所以總共需要跑的次數是：

2n/1 + 2n/2 + 2n/3 + ... + 2n/n = 2n × (1/1 + 1/2 + 1/3 + ... + 1/n) ≈ 2n ln(n)

也就是說，看起來要跑 n^2 次的雙層迴圈，實際上只會跑 O(n log n) 次。這種「對每個 i，只對它的倍數（或因數）做事」的迴圈模式，複雜度幾乎都能用調和級數分析法算出實際上是 O(n log n) ，而不是天真地當作 O(n^2) 。

// [來源：CISCON 2023]

// 概念示範：對每個 ary [i]，只掃描到乘積可能滿足條件為止就 break

sort(ary.begin(), ary.end());

int ans = 0;

for (int i = 0; i < n; i++){

    for (int j = i + 1; j < n; j++){

        if ((long long)ary[i].first * ary[j].first >= 2 * n) break;

        ans += valid(ary[i], ary[j]);

    }

}

看到「內層迴圈條件會提早 break」的暴力解，先別急著判它超時，用調和級數估一下真實的執行次數。這也是 1-1 提過的「由測資大小反推複雜度」的進階版：有時候表面的複雜度分析太悲觀，需要更細緻的數學工具才看得出真實的執行成本。

# 位元枚舉（Bit Enumeration）

通常是使用二進位來進行枚舉的技巧。位元枚舉通常使用迭代的方式，可以省略掉遞迴，但通常需要多一個 log 的時間來拆解二進位，所以其實在數字比較大的時候還是用遞迴比較好。

二進位常常拿來表示只有 0/1 的狀況，例如一般背包問題內的物品的狀態即為 0/1（是否被拿取）。

# 例題：CSES Apple Division

你現在有 n (1 ≤ n ≤ 20) 個蘋果，每一個蘋果都有一個重量 p_i(1 ≤ p_i ≤ 10^9) 。現在有兩個籃子，你必須把所有蘋果都放到這兩個籃子裡面，你可以選擇每一顆蘋果要放到哪一個籃子裡，但最後這兩個籃子的總重量要越接近越好，詢問最後這兩個籃子重量的最小差。

觀察到 n 非常小。每一個蘋果只有兩種可能，不是放在第一個籃子就是第二個籃子，狀態數總共有 2^n 個。可以用一個整數來代替我們狀態的集合：我們已知一個 int 有 32 位元，我們可以用第 i 個位元代表第 i 個蘋果，0 代表放第一個籃子，1 代表放第二個籃子。

最多只會有 2^n 種可能， 2^n 轉成二進位後剛好有 n+1 位數字（ 2^n 本身）， 2^n - 1 轉成二進位後剛好有 n 位數字，且這 n 位數字全部都是 1。我們從 0 跑到 2^n - 1 ，然後去看每一個數字的二進位的展開，就可以用來表示當前所有蘋果的狀態了，而這些狀態剛好有 2^n 種，所以這就等於我們把所有蘋果分配的可能性都枚舉了一遍，時間複雜度 O(2^n × n) 。

// [來源：本文補充，待替換]

int n; long long p[20];

long long best = LLONG_MAX;

for (int mask = 0; mask < (1 << n); mask++){

    long long sum1 = 0, total = 0;

    for (int i = 0; i < n; i++){

        total += p[i];

        if (mask & (1 << i)) sum1 += p[i];  // 第 i 位是 1，放進籃子二

    }

    long long sum2 = total - sum1;

    best = min(best, abs(sum1 - sum2));

}

這種「用一個整數的二進位表示子集合」的技巧，之後在 DP（狀態壓縮 DP，bitmask DP）也會大量出現，是很重要的基本功。

# 遞迴枚舉

顧名思義，就是用遞迴實作枚舉。寫起來十分直觀，但是要考慮到 stack overflow 的問題（RE）。

# 例題：Dreamoon and MRT

Dreamoon 在一條數線上會從某一個起點開始移動 m (1 ≤ m ≤ 25) 次，每一次移動了 d_i(1 ≤ d_i ≤ 10^5) 的距離，每一次移動有可能是往左也有可能是往右移動到數線上的某一個點，請問 Dreamoon 所在的數線上最少會有幾個點。

每一次移動會有兩種狀況，目前的左邊 / 右邊。所以我們需要知道兩個資料，分別是「目前的位置」以及「目前是第幾次移動」，這樣我們就可以推到下一次移動繼續做。

// [來源：本文補充，待替換]

set<long long> visited;

void dfs(long long pos, int step, int m, vector<int>& d){

    visited.insert(pos);

    if (step == m) return;

    dfs(pos + d[step], step + 1, m, d);  // 往右

    dfs(pos - d[step], step + 1, m, d);  // 往左

}

這種「每步有固定幾種選擇，遞迴列出所有分支」的寫法，正是本章開頭「窮舉每種可能」的標準模板，也是後面回溯法的基礎。

# 回溯法（Backtracking）

回溯法是一種經常被用在深度優先搜索（DFS）和廣度優先搜索（BFS）的技巧。本質就是：走不通就回頭。

程式中的 check 的函數其實就是回溯法的應用，回溯法的概念其實就是在確定已經不符合題目的條件就沒必要再繼續做下去，這也可以稱作是剪枝。

# 例題：一筆畫問題

給你一張圖，請你將字典序由小到大輸出所有能將這張圖一筆畫畫完的路徑，每一條邊只能被走過一次。

我們很明顯需要使用遞迴來跑所有走法。可以先預先建好邊，這樣寫起來就會好寫很多：

// [來源：CISCON 2023]

vector<int> edge[6];

// edge[1]={2,3,5};  edge[2]={1,3,5};  edge[3]={1,2,4,5};

// edge[4]={3,5};    edge[5]={1,2,3,4};

因為遞迴有非常非常好的回溯性質，所以特別適合用在這裡。每次遞迴就是測試目前這個點到下一個點之間的「邊」是否有走過，如果發現走過當然就是不走：

// [來源：CISCON 2023]

vector<int> edge[6];

bool vis[8][8]={};

void dfs(int depth,int np,string ans){

    if(depth==8){

        cout<<ans<<"\n";

        return ;

    }

    for(int i=0;i<edge[np].size();i++){

        if(vis[np][edge[np][i]]){

            continue;

        }

        vis[np][edge[np][i]]=1;

        vis[edge[np][i]][np]=1;

        dfs(depth+1,edge[np][i],ans+(char)(edge[np][i]+'0'));

        vis[np][edge[np][i]]=0;

        vis[edge[np][i]][np]=0 ;

    }

    return ;

}

關鍵的三行是回溯的精髓：

vis[np][edge[np][i]]=1;          // 走這條邊：標記已走過

dfs(depth+1,edge[np][i],...);    // 繼續往下走

vis[np][edge[np][i]]=0;          // 回頭後：把標記還原

「還原標記」是回溯法最重要也最容易漏掉的一步。 如果忘記把 vis 改回 0，遞迴回到上一層之後，這條邊就會被誤認為「已經走過」，導致漏掉合法的路徑。

# 例題：N 皇后

我拿了 APCS 的考古題「最多得分的皇后」來當回溯法的例題（詳細可見我原本的講義）。核心概念一樣是：每放一個皇后前，先檢查跟之前放的皇后會不會互相攻擊（同行、同列、同對角線），不合法就跳過，這就是剪枝 —— 提前放棄註定不會產生合法解的分支，不用等到最後才發現錯了。

#include<bits/stdc++.h>

using namespace std;

#define N 14

int q[N][N],n,ans=0,a[N];

void Queen(int k){

    if(k==n){// 終止條件

        int buffer=0;

        for(int i=0;i<n;i++){

            if(a[i]==-1) continue;

            buffer+=q[i][a[i]];

        }

        if(ans<buffer) ans=buffer;

    }else{

        for(int i=0;i<n;i++){

            bool t=1;

            for(int j=0;j<k;j++){

                if(a[j]==-1) continue;

                if(i==a[j] || abs(a[j]-i)==(k-j)){// 判斷皇后衝突

                    t=0;

                    break;

                }

            }

            if(t){

                a[k]=i;

                Queen(k+1);

            }

        }

        a[k]=-1;// 這行沒放皇后的情況

        Queen(k+1);

    }

}

int main(){

    cin>>n;

    for(int i=0;i<n;i++)

        for(int j=0;j<n;j++)

            cin>>q[i][j];

    Queen(0);

    cout<<ans;

}

觀察這個程式可能會覺得比上一題的程式碼看起來複雜不少，感覺也有些雜亂，有時候不需要把判斷都硬塞在同個函式裡，可以向上個程式一樣把判斷獨立拉出來自己設一個函式，呼叫函式然後再判斷是否符合條件，最後再回傳 true or false，這是我寫程式喜歡用的一個技巧，Debug 也會比較好找，容易分出一部份一部份的區塊逐一去尋找有問題的地方。

# 剪枝（Pruning）

就是在枚舉的過程中減少不必要的過程，通常用在遞迴上。主要概念就是，假設遞迴到一半的時候發現目前的狀態繼續遞迴下去的答案也是確定的。換句話說，如果遞迴到一半發現違反了先前訂的規則，那就不繼續遞迴。很像是從一棵滿滿的遞迴樹上從裡面剪掉幾個一定沒用的子樹。

# 例題：CSES Grid Paths

給你一個 7×7 的網格，你要從左上角走到左下角，一開始會輸入一個字串 s，如果第 i 個字元是 ? 表示第 i 步你可以隨意上下左右走，否則如果是 U, D, L, R 第 i 步就只能照指定的走，求有多少走法會將所有格子都走過剛好一次，在字元都是問號的情況下，走法會有 88418 種。

單純的 DFS！ 但單純的 DFS 枚舉的複雜度是 O(4^(n^2)) 超級大 —— 每一步都有 4 個方向可以選，走 n^2 步。想個好方法來剪枝。

這題完整的最佳剪枝需要用到連通性分析（例如判斷剩下的空格會不會被切成無法連通的兩塊），細節比較複雜，這裡先點出最基本、也最容易想到的兩種剪枝方向：

1. 邊界剪枝：一旦座標超出網格範圍，或準備踩到已經走過的格子，立刻停止這條路徑往下遞迴，不需要等到走完才發現錯誤。
2. 步數剪枝：如果目前走過的步數加上剩餘理論上最多能走的步數，都不可能達到「走滿全部格子」的目標，也可以提前放棄。

// [來源：本文補充，待替換]

bool used[7][7];

int dx[4]={-1,1,0,0}, dy[4]={0,0,-1,1};

long long ans = 0;

void dfs(int x, int y, int step, string& s){

    if (x < 0 || x >= 7 || y < 0 || y >= 7 || used[x][y]) return;  // 邊界剪枝

    used[x][y] = true;

    if (step == 48){ ans++; used[x][y] = false; return; }         // 走滿 7*7 個格子

    for (int dir = 0; dir < 4; dir++){

        char move = "UDLR"[dir];

        if (s[step] != '?' && s[step] != move) continue;          // 指定方向的剪枝

        dfs(x+dx[dir], y+dy[dir], step+1, s);

    }

    used[x][y] = false;

}

剪枝的效果來自於：越早發現一個分支不可能產生合法解，就能越早停止，省下底下整棵子樹的計算。同一題，有剪枝跟沒剪枝的差距可以是天壤之別 —— 沒剪枝可能幾分鐘都跑不完，剪對地方可能零點幾秒就出解。

判斷剪枝條件的訣竅：先想清楚題目的「合法性」到底是什麼，然後盡量把檢查合法性的時機提前，而不是等到整條路徑都走完才檢查。

# 折半枚舉（Meet in the Middle）

當資料規模大到 O(2^n) 無法完成（例如 n 到 30~40），但又還沒大到連 O(2^(n/2)) 都做不到時，可以考慮折半枚舉：把問題拆成兩半，各自窮舉子問題的解，再想辦法快速合併兩邊的結果。

# 核心想法

假設要窮舉 n 個元素的所有子集合（ 2^n 種），折半枚舉的做法是：

1. 把 n 個元素平分成兩半 A（前 n/2 個）與 B（後 n/2 個）
2. 分別窮舉 A 的所有子集合（ 2^(n/2) 種）與 B 的所有子集合（ 2^(n/2) 種）
3. 想辦法快速合併兩邊的結果（通常靠排序後二分搜，或用 map）

複雜度從 O(2^n) 降到 O(2^(n/2) × 某個合併成本) ，當合併成本是 O(log) 等級時，整體遠比原本的指數複雜度小很多。例如 n=36， 2^36 約 700 億，做不到；但 2^18 只有約 26 萬，兩邊窮舉後排序、二分搜合併，完全可行。

# 例題：子集合乘積（APCS 折半枚舉）

題目來源：AP325 P-2-9

輸入 n 個正整數 A [1..n]，以及一個質數 P，請計算 A 中元素各種組合中，有多少種組合其相乘積除以 P 的餘數等於 1。每個元素可以選取或不選取但不可重複選，A 中的數字可能重複。P≤1000000009，0 < n < 37，且假設 A 元素皆小於 P。

（說明：乘積等於 1 的組合有 (1)、(1)、(1,1)、(2,6)、(1,2,6)、(1,2,6)、(1,1,2,6) 共 7 種）

思路：n 最大到 36，直接窮舉全部子集合是 O(2^36) ，不可行。折半枚舉：把 n 個數字平分為兩半 A 與 B，我們要找的解（子集合乘積等於 1）有三種可能：

1. 解完全落在 A 中
2. 解完全落在 B 中
3. 解跨越 A、B 兩端（兩邊各選一些元素，乘起來剛好是 1）

對 A 與 B 分別窮舉它們的子集合乘積，就能算出情況 1、2。對於情況 3（跨兩邊），利用模逆元：把其中一邊（例如 B）的所有子集合乘積排序，對每一個 A 的子集合乘積 x，在 B 的子集合乘積中去搜尋 x 的模逆元 y（使得 xy ≡ 1 (mod P) 的 y）。

這裡有一點必須留意，我們要把 B 的子集合乘積中相同的乘積予以合併，否則若相同乘積太多，一個 x 需要搜尋很多的模逆元就會太花時間。

複雜度分析：對 n/2 個元素窮舉子集合需要 O(2^(n/2)) ，兩邊都做所以乘以 2；排序需要 O(n×2^(n/2)) ；接著 2^(n/2) 個數字在 2^(n/2) 個數字中做二分搜，需要的時間是 O(n×2^(n/2)) ，所以總時間複雜度是 O(n×2^(n/2)) ，這比起單純窮舉 O(2^n) 要快得多了。

// [來源：AP325]

// subset product = 1 mod P, O(n*2^(n/2)), using map

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

// recursive generate product of subsets of v[0..i]

// current product=prod, result stored in M

void rec(vector<LL> &v, int i, LL prod, map<LL,LL> &M, LL p) {

    if (i>=v.size()) { // terminal condition

        M[prod] += 1; // insert into map

        return;

    }

    rec(v, i+1, (prod*v[i])%p, M, p); // select v[i]

    rec(v, i+1, prod, M, p); // discard v[i]

    return;

}

// find x^y mod P

LL exp(LL x, LL y, LL p) {

    if (y==0) return 1;

    if (y & 1) return (exp(x, y-1,p)*x)%p;

    // otherwise y is even

    LL t=exp(x, y/2, p);

    return (t*t)%p;

}

int main() {

    int i, n;

    vector<LL> a, b; // input data

    LL p;

    scanf("%d%lld", &n, &p);

    for (i=0;i<n/2;i++) { // half in a

        LL t;

        scanf("%lld", &t);

        a.push_back(t);

    }

    for ( ;i<n;i++) { // half in b

        LL t;

        scanf("%lld", &t);

        b.push_back(t);

    }

    map<LL,LL> M1, M2;

    rec(a,0,1,M1,p); // all subsets of a

    rec(b,0,1,M2,p); // all subsets of b

    M1[1] -= 1; // empty set was counted as product 1

    M2[1] -= 1; // empty set

    LL ans = (M1[1]+M2[1])%p; // the number of 1 in both sides

    // for each x in M1, find its inverse in M2

    for (auto e: M1) {

        if (e.second==0) continue;

        LL y = exp(e.first, p-2, p); // inverse

        if (M2.count(y))

            ans = (ans + e.second * M2[y]) % p;

    }

    printf("%lld\n", ans);

    return 0;

}

模逆元是這題的關鍵數學工具：對於任何一個正整數 a，它的模 P 乘法反元素就是滿足 (a * b) % P = 1 的整數 b。根據費馬小定理，若 P 為質數，對任意正整數 a， (a^(P-2)) % P 就是 a 在 [1, P-1] 區間的唯一乘法反元素，可以用快速幕在 O(log P) 內算出。快速幕的技巧會在下一章 1-5 貪心演算法 之後的章節陸續用到，這裡先看到它被拿來解決「跨兩邊配對」的問題。

# 判斷能不能用折半枚舉

看到 n 大約落在 30~40 這個區間、需要窮舉子集合或排列的題目，且直接窮舉的 O(2^n) 或 O(n!) 明顯超時，但拆成兩半各自窮舉 O(2^(n/2)) 卻可以接受，就是折半枚舉的典型場景。合併兩半結果的手法通常是「排序 + 二分搜」或「用 map／set 查表」。

# 小結

這章從「單純的暴力」出發，逐步走向「聰明的暴力」：

窮舉暴搜看似「不聰明」，但它其實是所有優化技巧的起點 —— 先寫出正確的暴力解，再一步步觀察哪裡可以剪、哪裡可以拆、哪裡有重複可以避免，這條路徑幾乎貫穿了整個演算法學習過程，也是 debug 時驗證答案最可靠的方式。

下一章要講貪心演算法：如果窮舉是「把所有可能都看過一遍」，貪心就是相反的極端 —— 每一步都只看眼前最好的選擇，完全不回頭。什麼時候這樣做是安全的？下一章會給出證明方法。

# 練習題

（之後補上）