C++全排列問題

全排列問題是回溯算法的一個(gè)典型應(yīng)用。它的定義是在給定一個(gè)集合（如一個(gè)數(shù)組或字符串）的情況下，找出這個(gè)集合中元素的所有可能的排列。

表 13-2 列舉了幾個(gè)示例數(shù)據(jù)，包括輸入數(shù)組和對(duì)應(yīng)的所有排列。

表 13-2   數(shù)組與鏈表的效率對(duì)比

無相等元素的情況

從回溯算法的角度看，我們可以把生成排列的過程想象成一系列選擇的結(jié)果。假設(shè)輸入數(shù)組為 $[1,2,3]$ ，如果我們先選擇 $1$、再選擇 $3$、最后選擇 $2$ ，則獲得排列 $[1,3,2]$ 。回退表示撤銷一個(gè)選擇，之后繼續(xù)嘗試其他選擇。

從回溯代碼的角度看，候選集合 choices 是輸入數(shù)組中的所有元素，狀態(tài) state 是直至目前已被選擇的元素。請(qǐng)注意，每個(gè)元素只允許被選擇一次，因此 state 中的所有元素都應(yīng)該是唯一的。

如圖 13-5 所示，我們可以將搜索過程展開成一個(gè)遞歸樹，樹中的每個(gè)節(jié)點(diǎn)代表當(dāng)前狀態(tài) state 。從根節(jié)點(diǎn)開始，經(jīng)過三輪選擇后到達(dá)葉節(jié)點(diǎn)，每個(gè)葉節(jié)點(diǎn)都對(duì)應(yīng)一個(gè)排列。

圖 13-5   全排列的遞歸樹

1.   重復(fù)選擇剪枝

為了實(shí)現(xiàn)每個(gè)元素只被選擇一次，我們考慮引入一個(gè)布爾型數(shù)組 selected ，其中 selected[i] 表示 choices[i] 是否已被選擇，并基于它實(shí)現(xiàn)以下剪枝操作。

• 在做出選擇 choice[i] 后，我們就將 selected[i] 賦值為 $\text{True}$ ，代表它已被選擇。
• 遍歷選擇列表 choices 時(shí)，跳過所有已被選擇過的節(jié)點(diǎn)，即剪枝。

如圖 13-6 所示，假設(shè)我們第一輪選擇 1 ，第二輪選擇 3 ，第三輪選擇 2 ，則需要在第二輪剪掉元素 1 的分支，在第三輪剪掉元素 1 和元素 3 的分支。

圖 13-6   全排列剪枝示例

觀察圖 13-6 發(fā)現(xiàn)，該剪枝操作將搜索空間大小從 $O(n^n)$ 降低至 $O(n!)$ 。

2.   代碼實(shí)現(xiàn)

想清楚以上信息之后，我們就可以在框架代碼中做“完形填空”了。為了縮短代碼行數(shù)，我們不單獨(dú)實(shí)現(xiàn)框架代碼中的各個(gè)函數(shù)，而是將他們展開在 backtrack() 函數(shù)中。

permutations_i.cpp

/* 回溯算法：全排列 I */
void backtrack(vector<int> &state, const vector<int> &choices, vector<bool> &selected, vector<vector<int>> &res) {
    // 當(dāng)狀態(tài)長(zhǎng)度等于元素?cái)?shù)量時(shí)，記錄解
    if (state.size() == choices.size()) {
        res.push_back(state);
        return;
    }
    // 遍歷所有選擇
    for (int i = 0; i < choices.size(); i++) {
        int choice = choices[i];
        // 剪枝：不允許重復(fù)選擇元素 且 不允許重復(fù)選擇相等元素
        if (!selected[i]) {
            // 嘗試：做出選擇，更新狀態(tài)
            selected[i] = true;
            state.push_back(choice);
            // 進(jìn)行下一輪選擇
            backtrack(state, choices, selected, res);
            // 回退：撤銷選擇，恢復(fù)到之前的狀態(tài)
            selected[i] = false;
            state.pop_back();
        }
    }
}

/* 全排列 I */
vector<vector<int>> permutationsI(vector<int> nums) {
    vector<int> state;
    vector<bool> selected(nums.size(), false);
    vector<vector<int>> res;
    backtrack(state, nums, selected, res);
    return res;
}

考慮相等元素的情況

假設(shè)輸入數(shù)組為 $[1,1,2]$ 。為了方便區(qū)分兩個(gè)重復(fù)元素 $1$ ，我們將第二個(gè) $1$ 記為 $\hat{1}$ 。

如圖 13-7 所示，上述方法生成的排列有一半都是重復(fù)的。

圖 13-7   重復(fù)排列

那么如何去除重復(fù)的排列呢？最直接地，考慮借助一個(gè)哈希表，直接對(duì)排列結(jié)果進(jìn)行去重。然而這樣做不夠優(yōu)雅，因?yàn)樯芍貜?fù)排列的搜索分支是沒有必要的，應(yīng)當(dāng)被提前識(shí)別并剪枝，這樣可以進(jìn)一步提升算法效率。

1.   相等元素剪枝?

觀察圖 13-8 ，在第一輪中，選擇 $1$ 或選擇 $\hat{1}$ 是等價(jià)的，在這兩個(gè)選擇之下生成的所有排列都是重復(fù)的。因此應(yīng)該把 $\hat{1}$ 剪枝掉。

同理，在第一輪選擇 $2$ 之后，第二輪選擇中的 $1$ 和 $\hat{1}$ 也會(huì)產(chǎn)生重復(fù)分支，因此也應(yīng)將第二輪的 $\hat{1}$ 剪枝。

本質(zhì)上看，我們的目標(biāo)是在某一輪選擇中，保證多個(gè)相等的元素僅被選擇一次。

圖 13-8   重復(fù)排列剪枝

2.   代碼實(shí)現(xiàn)

在上一題的代碼的基礎(chǔ)上，我們考慮在每一輪選擇中開啟一個(gè)哈希表 duplicated ，用于記錄該輪中已經(jīng)嘗試過的元素，并將重復(fù)元素剪枝。

permutations_ii.cpp

/* 回溯算法：全排列 II */
void backtrack(vector<int> &state, const vector<int> &choices, vector<bool> &selected, vector<vector<int>> &res) {
    // 當(dāng)狀態(tài)長(zhǎng)度等于元素?cái)?shù)量時(shí)，記錄解
    if (state.size() == choices.size()) {
        res.push_back(state);
        return;
    }
    // 遍歷所有選擇
    unordered_set<int> duplicated;
    for (int i = 0; i < choices.size(); i++) {
        int choice = choices[i];
        // 剪枝：不允許重復(fù)選擇元素 且 不允許重復(fù)選擇相等元素
        if (!selected[i] && duplicated.find(choice) == duplicated.end()) {
            // 嘗試：做出選擇，更新狀態(tài)
            duplicated.emplace(choice); // 記錄選擇過的元素值
            selected[i] = true;
            state.push_back(choice);
            // 進(jìn)行下一輪選擇
            backtrack(state, choices, selected, res);
            // 回退：撤銷選擇，恢復(fù)到之前的狀態(tài)
            selected[i] = false;
            state.pop_back();
        }
    }
}

/* 全排列 II */
vector<vector<int>> permutationsII(vector<int> nums) {
    vector<int> state;
    vector<bool> selected(nums.size(), false);
    vector<vector<int>> res;
    backtrack(state, nums, selected, res);
    return res;
}

假設(shè)元素兩兩之間互不相同，則 $n$ 個(gè)元素共有 $n!$ 種排列（階乘）；在記錄結(jié)果時(shí)，需要復(fù)制長(zhǎng)度為 $n$ 的列表，使用 $O(n)$ 時(shí)間。因此時(shí)間復(fù)雜度為 $O(n!n)$ 。

最大遞歸深度為 $n$ ，使用 $O(n)$ 棧幀空間。selected 使用 $O(n)$ 空間。同一時(shí)刻最多共有 $n$ 個(gè) duplicated ，使用 $O(n^2)$ 空間。因此空間復(fù)雜度為 $O(n^2)$ 。

3.   兩種剪枝對(duì)比

請(qǐng)注意，雖然 selected 和 duplicated 都用作剪枝，但兩者的目標(biāo)是不同的。

• 重復(fù)選擇剪枝：整個(gè)搜索過程中只有一個(gè) selected 。它記錄的是當(dāng)前狀態(tài)中包含哪些元素，作用是避免某個(gè)元素在 state 中重復(fù)出現(xiàn)。
• 相等元素剪枝：每輪選擇（即每個(gè)開啟的 backtrack 函數(shù)）都包含一個(gè) duplicated 。它記錄的是在遍歷中哪些元素已被選擇過，作用是保證相等元素只被選擇一次。

圖 13-9 展示了兩個(gè)剪枝條件的生效范圍。注意，樹中的每個(gè)節(jié)點(diǎn)代表一個(gè)選擇，從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑上的各個(gè)節(jié)點(diǎn)構(gòu)成一個(gè)排列。

圖 13-9   兩種剪枝條件的作用范圍