C++全排列問題

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

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

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

無相等元素的情況

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

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

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

圖 13-5   全排列的遞歸樹

1.   重復選擇剪枝

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

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

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

圖 13-6   全排列剪枝示例

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

2.   代碼實現(xiàn)

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

permutations_i.cpp

/* 回溯算法：全排列 I */
void backtrack(vector<int> &state, const vector<int> &choices, vector<bool> &selected, vector<vector<int>> &res) {
    // 當狀態(tài)長度等于元素數(shù)量時，記錄解
    if (state.size() == choices.size()) {
        res.push_back(state);
        return;
    }
    // 遍歷所有選擇
    for (int i = 0; i < choices.size(); i++) {
        int choice = choices[i];
        // 剪枝：不允許重復選擇元素 且 不允許重復選擇相等元素
        if (!selected[i]) {
            // 嘗試：做出選擇，更新狀態(tài)
            selected[i] = true;
            state.push_back(choice);
            // 進行下一輪選擇
            backtrack(state, choices, selected, res);
            // 回退：撤銷選擇，恢復到之前的狀態(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ù)組為 $[1,1,2]$ 。為了方便區(qū)分兩個重復元素 $1$ ，我們將第二個 $1$ 記為 $\hat{1}$ 。

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

圖 13-7   重復排列

那么如何去除重復的排列呢？最直接地，考慮借助一個哈希表，直接對排列結(jié)果進行去重。然而這樣做不夠優(yōu)雅，因為生成重復排列的搜索分支是沒有必要的，應當被提前識別并剪枝，這樣可以進一步提升算法效率。

1.   相等元素剪枝?

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

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

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

圖 13-8   重復排列剪枝

2.   代碼實現(xiàn)

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

permutations_ii.cpp

/* 回溯算法：全排列 II */
void backtrack(vector<int> &state, const vector<int> &choices, vector<bool> &selected, vector<vector<int>> &res) {
    // 當狀態(tài)長度等于元素數(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];
        // 剪枝：不允許重復選擇元素 且 不允許重復選擇相等元素
        if (!selected[i] && duplicated.find(choice) == duplicated.end()) {
            // 嘗試：做出選擇，更新狀態(tài)
            duplicated.emplace(choice); // 記錄選擇過的元素值
            selected[i] = true;
            state.push_back(choice);
            // 進行下一輪選擇
            backtrack(state, choices, selected, res);
            // 回退：撤銷選擇，恢復到之前的狀態(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;
}

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

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

3.   兩種剪枝對比

請注意，雖然 selected 和 duplicated 都用作剪枝，但兩者的目標是不同的。

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

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

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