[LeetCode] 47. Permutations II 全排列之二

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]

這道題是之前那道 Permutations 的延伸，由于輸入數(shù)組有可能出現(xiàn)重復(fù)數(shù)字，如果按照之前的算法運算，會有重復(fù)排列產(chǎn)生，我們要避免重復(fù)的產(chǎn)生，在遞歸函數(shù)中要判斷前面一個數(shù)和當(dāng)前的數(shù)是否相等，如果相等，且其對應(yīng)的 visited 中的值為1，當(dāng)前的數(shù)字才能使用（下文中會解釋這樣做的原因），否則需要跳過，這樣就不會產(chǎn)生重復(fù)排列了，代碼如下：

解法一：

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> out, visited(nums.size(), 0);
        sort(nums.begin(), nums.end());
        permuteUniqueDFS(nums, 0, visited, out, res);
        return res;
    }
    void permuteUniqueDFS(vector<int>& nums, int level, vector<int>& visited, vector<int>& out, vector<vector<int>>& res) {
        if (level >= nums.size()) {res.push_back(out); return;}
        for (int i = 0; i < nums.size(); ++i) {
            if (visited[i] == 1) continue;
            if (i > 0 && nums[i] == nums[i - 1] && visited[i - 1] == 0) continue;
            visited[i] = 1;
            out.push_back(nums[i]);
            permuteUniqueDFS(nums, level + 1, visited, out, res);
            out.pop_back();
            visited[i] = 0;
        }
    }
};

在使用上面的方法的時候，一定要能弄清楚遞歸函數(shù)的 for 循環(huán)中兩個 if 的剪枝的意思。在此之前，要弄清楚 level 的含義，這里用數(shù)組 out 來拼排列結(jié)果，level就是當(dāng)前已經(jīng)拼成的個數(shù)，其實就是 out 數(shù)組的長度。我們看到，for 循環(huán)的起始是從0開始的，而本題的解法二，三，四都是用了一個 start 變量，從而 for 循環(huán)都是從 start 開始，一定要分清楚 start 和本解法中的 level 的區(qū)別。由于遞歸的 for 都是從0開始，難免會重復(fù)遍歷到數(shù)字，而全排列不能重復(fù)使用數(shù)字，意思是每個 nums 中的數(shù)字在全排列中只能使用一次（當(dāng)然這并不妨礙 nums 中存在重復(fù)數(shù)字）。不能重復(fù)使用數(shù)字就靠 visited 數(shù)組來保證，這就是第一個 if 剪枝的意義所在。關(guān)鍵來看第二個 if 剪枝的意義，這里說當(dāng)前數(shù)字和前一個數(shù)字相同，且前一個數(shù)字的 visited 值為0的時候，必須跳過。這里的前一個數(shù) visited 值為0，并不代表前一個數(shù)字沒有被處理過，也可能是遞歸結(jié)束后恢復(fù)狀態(tài)時將 visited 值重置為0了，實際上就是這種情況，下面打印了一些中間過程的變量值，如下所示：

注意看這里面的 skipped 1 表示的是第一個 if 剪枝起作用的地方，skipped 2 表示的是第二個 if 剪枝起作用的地方。我們主要關(guān)心的是第二個 if 剪枝，看上方第一個藍(lán)色標(biāo)記的那行，再上面的紅色一行表示在 level = 1, i = 1 時遞歸調(diào)用結(jié)束后，恢復(fù)到起始狀態(tài)，那么此時 out 數(shù)組中只有一個1，后面的2已經(jīng)被 pop_back() 了，當(dāng)然對應(yīng)的 visited 值也重置為0了，這種情況下需要剪枝，當(dāng)然不能再一次把2往里加，因為這種情況在遞歸中已經(jīng)加入到結(jié)果 res 中了，所以到了 level = 1, i = 2 的狀態(tài)時，nums[i] == nums[i-1] && visited[i-1] == 0 的條件滿足了，剪枝就起作用了，這種重復(fù)的情況就被剪掉了。

還有一種比較簡便的方法，在 Permutations 的基礎(chǔ)上稍加修改，用 TreeSet 來保存結(jié)果，利用其不會有重復(fù)項的特點，然后在遞歸函數(shù)中 swap 的地方，判斷如果i和 start 不相同，但是 nums[i] 和 nums[start] 相同的情況下跳過，繼續(xù)下一個循環(huán)，參見代碼如下：

解法二：

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        set<vector<int>> res;
        permute(nums, 0, res);
        return vector<vector<int>> (res.begin(), res.end());
    }
    void permute(vector<int>& nums, int start, set<vector<int>>& res) {
        if (start >= nums.size()) res.insert(nums);
        for (int i = start; i < nums.size(); ++i) {
            if (i != start && nums[i] == nums[start]) continue;
            swap(nums[i], nums[start]);
            permute(nums, start + 1, res);
            swap(nums[i], nums[start]);
        }
    }
};

對于上面的解法，你可能會有疑問，我們不是在 swap 操作之前已經(jīng)做了剪枝了么，為什么還是會有重復(fù)出現(xiàn)，以至于還要用 TreeSet 來取出重復(fù)呢。總感覺使用 TreeSet 去重復(fù)有點耍賴，可能并沒有探究到本題深層次的內(nèi)容。這是很好的想法，首先嘗試將上面的 TreeSet 還原為 vector，并且在主函數(shù)調(diào)用遞歸之前給 nums 排個序（代碼參見評論區(qū)三樓），然后測試一個最簡單的例子：[1, 2, 2]，得到的結(jié)果為：

[[1,2,2], [2,1,2], [2,2,1], [2,2,1],  [2,1,2]]

我們發(fā)現(xiàn)有重復(fù)項，那么剪枝究竟在做些什么，怎么還是沒法防止重復(fù)項的產(chǎn)生！那個剪枝只是為了防止當(dāng) start = 1, i = 2 時，將兩個2交換，這樣可以防止 {1, 2, 2} 被加入兩次。但是沒法防止其他的重復(fù)情況，要鬧清楚為啥，需要仔細(xì)分析一些中間過程，下面打印了一些中間過程的變量：

問題出在了遞歸調(diào)用之后的還原狀態(tài)，參見上面的紅色的兩行，當(dāng) start = 0, i = 2 時，nums 已經(jīng)還原到了 {1, 2, 2} 的狀態(tài)，此時 nums[start] 不等于 nums[i]，剪枝在這已經(jīng)失效了，那么交換后的 {2, 2, 1} 還會被存到結(jié)果 res 中，而這個狀態(tài)在之前就已經(jīng)存過了一次。

注意到當(dāng) start = 0, i = 1 時，nums 交換之后變成了 {2, 1, 2}，如果能保持這個狀態(tài)，那么當(dāng) start = 0, i = 2 時，此時 nums[start] 就等于 nums[i] 了，剪枝操作就可以發(fā)揮作用了。怎么才能當(dāng)遞歸結(jié)束后，不還原成為交換之前的狀態(tài)的呢？答案就是不進(jìn)行還原，這樣還是能保存為之前交換后的狀態(tài)。只是將最后一句 swap(nums[i], nums[start]) 刪掉是不行的，因為遞歸函數(shù)的參數(shù) nums 是加了&號，就表示引用了，那么之前調(diào)用遞歸函數(shù)之前的 nums 在遞歸函數(shù)中會被修改，可能還是無法得到我們想要的順序，所以要把遞歸函數(shù)的 nums 參數(shù)的&號也同時去掉才行，參見代碼如下：

解法三：

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        permute(nums, 0, res);
        return res;
    }
    void permute(vector<int> nums, int start, vector<vector<int>>& res) {
        if (start >= nums.size()) res.push_back(nums);
        for (int i = start; i < nums.size(); ++i) {
            if (i != start && nums[i] == nums[start]) continue;
            swap(nums[i], nums[start]);
            permute(nums, start + 1, res);
        }
    }
};

好，再測試下 [1, 2, 2] 這個例子，并且把中間變量打印出來：

明顯發(fā)現(xiàn)短了許多，說明剪枝發(fā)揮了作用，看上面紅色部分，當(dāng) start = 0, i = 1 時，遞歸函數(shù)調(diào)用完了之后，nums 數(shù)組保持了 {2, 1, 2} 的狀態(tài)，那么到 start = 0, i = 2 的時候，nums[start] 就等于 nums[i] 了，剪枝操作就可以發(fā)揮作用了。

這時候你可能會想，調(diào)用完遞歸不恢復(fù)狀態(tài)，感覺怪怪的，跟哥的遞歸模版不一樣啊，容易搞混啊，而且一會加&號，一會不加的，這尼瑪誰能分得清啊。別擔(dān)心，I gotcha covered! 好，既然還是要恢復(fù)狀態(tài)的話，就只能從剪枝入手了，原來那種 naive 的剪枝方法肯定無法使用，矛盾的焦點還是在于，當(dāng) start = 0, i = 2 時，nums 被還原成了 start = 0, i = 1 的交換前的狀態(tài) {1, 2, 2}，這個狀態(tài)已經(jīng)被處理過了，再去處理一定會產(chǎn)生重復(fù)，怎么才知道這被處理過了呢，當(dāng)前的 i = 2，需要往前去找是否有重復(fù)出現(xiàn)，由于數(shù)組已經(jīng)排序過了，如果有重復(fù)，那么前面數(shù)一定和當(dāng)前的相同，所以用一個 while 循環(huán)，往前找和 nums[i] 相同的數(shù)字，找到了就停下，當(dāng)然如果小于 start 了也要停下，那么如果沒有重復(fù)數(shù)字的話，j 一定是等于 start-1 的，那么如果不等于的話，就直接跳過就可以了，這樣就可以去掉所有的重復(fù)啦，參見代碼如下：

解法四：

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        permute(nums, 0, res);
        return res;
    }
    void permute(vector<int>& nums, int start, vector<vector<int>>& res) {
        if (start >= nums.size()) res.push_back(nums);
        for (int i = start; i < nums.size(); ++i) {
            int j = i - 1;
            while (j >= start && nums[j] != nums[i]) --j;
            if (j != start - 1) continue;
            swap(nums[i], nums[start]);
            permute(nums, start + 1, res);
            swap(nums[i], nums[start]);
        }
    }
};

同樣，我們再測試下 [1, 2, 2] 這個例子，并且把中間變量打印出來：

到 start = 0, i = 2 的時候，j 此時等于1了，明顯不是 start-1，說明有重復(fù)了，直接 skip 掉，這樣剪枝操作就可以發(fā)揮作用了。

之前的 Permutations 中的解法三也可以用在這里，只不過需要借助 TreeSet 來去重復(fù)，博主還未想出其他不用集合的去重復(fù)的方法，哪位看官大神們知道的話，請一定要留言告知博主，參見代碼如下：

解法五：

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        if (nums.empty()) return vector<vector<int>>(1, vector<int>());
        set<vector<int>> res;
        int first = nums[0];
        nums.erase(nums.begin());
        vector<vector<int>> words = permuteUnique(nums);
        for (auto &a : words) {
            for (int i = 0; i <= a.size(); ++i) {
                a.insert(a.begin() + i, first);
                res.insert(a);
                a.erase(a.begin() + i);
            }
        }   
        return vector<vector<int>> (res.begin(), res.end());
    }
};

之前的 Permutations 中的解法四博主沒法成功修改使其可以通過這道題，即便是將結(jié)果 res 用 TreeSet 來去重復(fù)，還是不對。同樣，哪位看官大神們知道的話，請一定要留言告知博主。后經(jīng)過微信公眾號上的熱心網(wǎng)友 hahaboy 的提醒下，可以通過加上一個剪枝從而通過這道題，在最中間的 for 循環(huán)的最后，判斷若 num 等于 t[i]，直接 break 掉當(dāng)前循環(huán)，否則會產(chǎn)生重復(fù)項，參見代碼如下：

解法六：

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res{{}};
        for (int num : nums) {
            for (int k = res.size(); k > 0; --k) {
                vector<int> t = res.front();
                res.erase(res.begin());
                for (int i = 0; i <= t.size(); ++i) {
                    vector<int> one = t;
                    one.insert(one.begin() + i, num);
                    res.push_back(one);
                    if (i < t.size() && num == t[i]) break;
                }
            }
        }
        return res;
    }
};

之前的 Permutations 中的解法五卻可以原封不動的搬到這道題來，看來自帶的 next_permutation() 函數(shù)就是叼啊，自帶去重復(fù)功能，叼叼叼！參見代碼如下：

解法七：

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        res.push_back(nums);
        while (next_permutation(nums.begin(), nums.end())) {
            res.push_back(nums);
        }
        return res;
    }
};

到此這篇關(guān)于C++實現(xiàn)LeetCode(47.全排列之二)的文章就介紹到這了,更多相關(guān)C++實現(xiàn)全排列之二內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！