題目網址：https://leetcode.cn/problems/permutations-ii/

題意：給一含重複數的 array nums, 按任意順序返回所有不重複的排列。

Solution：

想法：類似 46. Permutations, 只是要排除掉相同數當頭
e.g. [1, 1, 2]

  • 1 當頭 : [1, 1, 2], [1, 2, 1]
  • 1 當頭 : [1, 1, 2], [1, 1, 2]
    ➔ 重複排列, 故要記住哪些數當過開頭, 若後面遇到做過開頭的數則不做 swap, 直接跳過
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        dfs(nums, 0, nums.size());
        return res;
    }

private:
    vector<vector<int>> res;

    void dfs(vector<int>& nums, const int i, const int n){
        if (i == n) {
            res.emplace_back(nums);
            return;
        }

        unordered_set<int> s;

        for (int j = i; j < n; ++j) {
            if (s.find(nums[j]) != s.end()) {
                continue; // 避免重複排列
            }

            s.emplace(nums[j]);

            swap(nums[i], nums[j]);
            dfs(nums, i + 1, n);
            swap(nums[i], nums[j]);
        }
    }
};
  • time：$O(n \cdot n!)$ ➔ 總共 $n!$ 種排列, 每一種要 $O(n)$
  • space：$O(n \cdot n!)$ ➔ $O(n) + O(n \cdot n!)$
    • $O(n)$：dfs() 遞迴最大深度
    • $O(n \cdot n!)$：最多 $n!$ 種排列, 每種排列的長度都為 n