LeetCode 47. Permutations II [Medium] [C++] 解題筆記

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

EX:

        Input: [1,1,2]

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

想法:

    這題是 46. Permutations 的進階題，差別在於 46 題不會出現重複的元素而這題可能有重複元素，因此這題的

重點在於怎摸避免重複的解，通常要避免列舉重複的解我們可以在列舉時限制每個位置同樣的元素只能夠列舉一次，而為了方便

檢查同樣的元素是否已經在當前位置列舉過，我們可以將數列排序好之後只需要檢查當前元素是否與前一元素相同

且前一元素在此次列舉中尚未使用，即可知道此元素是否可以列舉。

完整程式碼:

class Solution {
private:
    vector<vector<int>> res;
public:
    void dfs(vector<int>& nums, vector<bool>& use, vector<int>& cur) {
        if (cur.size() == nums.size()) {
            res.emplace_back(cur);
            return;
        }
        
        for (int i = 0; i < nums.size(); i++) {
            if (use[i]) { continue; }
            if (i > 0 && nums[i] == nums[i-1] && !use[i-1]) { continue; }
            use[i] = true;
            cur.emplace_back(nums[i]);
            dfs(nums, use, cur);
            cur.pop_back();
            use[i] = false;
        }
        return;
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<bool> use(nums.size(), false);
        vector<int> cur;
        dfs(nums, use, cur);
        return res;
    }
};