WEI-CHENG CHEN

說明

跟 46 差別是，她不可以有重複答案

而處裡重錄的方式，是要額外用一個 set 紀錄(會跟 40 不同)

因為 47 用的是交換法，在交換法中，我們不再從左至右固定地挑選元素，而是通過「交換不同位置」來讓所有元素輪流出現在每個位置上。但這樣就可能讓相同的數字出現在不同的位置上，形成重複的排列。

🧩 原因關鍵在於：交換後的順序是浮動

舉例：

你從 start = 0 開始產生排列：

• i = 0，交換 nums[0] 和 nums[0] → [1, 1, 2] ✅
• i = 1，交換 nums[0] 和 nums[1] → [1, 1, 2] 🚨 重複了！

你明明已經用過 [1, 1, 2]，怎麼又來一組？因為你只是靠 i > start && nums[i] == nums[i - 1] 判斷「當前這一個是不是重複」，但在「交換」的情況下，它可能是從別的分支 swap 過來的！

解法

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end()); // 一定要排序
        vector<vector<int>> ans;
        backtracking(ans, nums, 0);
        return ans;
    }

    void backtracking(vector<vector<int>> &ans, vector<int>& nums, int start){
        // 終止條件
        if(start==nums.size()){
            ans.push_back(nums);
            return;
        }
        unordered_set<int> used; // 記錄當層出現過的值

        for(int i=start;i<nums.size();i++){
            if (used.count(nums[i])) continue; // 該層已經出現過，跳過
            used.insert(nums[i]);

            swap(nums[i], nums[start]);
            backtracking(ans, nums, start+1);
            swap(nums[i], nums[start]);
        }
    }
};