遞廻枚舉

簡介

上一個章節我們介紹了遞迴的概念，這一章節我們將介紹如何使用遞迴來枚舉所有可能的結果。

就像是 枚舉 章節一樣，遞迴枚舉也是一種枚舉的方法，但是遞迴枚舉的好處是可以更容易的處理較為複雜的情況，幾乎可以解決所有的枚舉問題。常常在不知道如何枚舉的情況下，可以考慮使用遞迴枚舉。

例題

給定 $n$ 個集合，每個集合中有 $a_i$ 個數字，如果要從每個集合中各選擇一個數字，有多少種選擇方式使得這些數字的乘積為 $x$？

$1 \leq n^{a_i} \leq 10^5$，$1 \leq x \leq 10^{18}$

看完題敘之後，發現之前在 枚舉 單元中介紹的基本枚舉和位元枚舉都無法解決這個問題，因為這個問題的集合數量和每個集合中的數字個數都不固定。

這時候我們可以考慮使用遞迴枚舉，我們可以使用一個變數 $i$ 來表示目前在第 $i$ 個集合，然後遞迴的枚舉下一個集合的數字，直到枚舉完所有的集合。

// i 表示目前在第 i 個集合
// val 表示目前的乘積
void rec(int i, int val) {
    // 如果已經枚舉完所有的集合
    if (i == n) {
        // 更新答案並退出遞迴
        if (val == x) ans++;
        return;
    }
    // 枚舉第 i 個集合的每個數字
    for (int j = 0; j < a[i]; j++) {
        // 遞迴枚舉進入下一個集合
        rec(i + 1, val * a[i][j]);
    }
}

如果把遞迴過程畫出來觀察的話可以看到一個叫做遞迴樹的結構，每一個節點對應一個「結果」，而經過下一個「抉擇」後又會再透過邊連接到下一個結果，直到遞迴終止桃件。

再仔細一點觀察的話，可以發現這個遞迴樹大致上分成三層，第一層是抉擇第一個集合的數字，第二層是抉擇第二個集合的數字。

如果想在第一個集合選擇第 $1$ 個數字，第二個集合選擇第 $2$ 個數字，第三個集合選擇第 $1$ 個數字，可以看到下圖紫色區塊的遞迴路徑。

而最底下的節點就是一個「最終結果」，這個結果是由每一層的抉擇所組成的，只要計算這個結果是否符合題目要求就可以了。

如果理解上面的內容，應該就很容易搞懂遞迴枚舉如何嘗試所有的可能結果了的概念了。