###### tags: `LeetCode` `Medium` `DFS` `Recursion`
# LeetCode #47 [Permutation II](https://leetcode.com/problems/permutations-ii/)
### (Medium)

給定一個可包含重複數字的序列 nums ，按任意順序 返回所有不重複的全排列。

---

要解決的是重複問題, 比如: 輸入為[1-1,1-2,2]時的重複值{2, 1-1, 1-2}與{2, 1-2, 1-1}。

除了單純的使用數組紀錄使用過的數字外(只能避免將自己重複插入暫存數組中), 另外的判斷條件就是:

(i>0 && nums[i]==nums[i-1] && !used[i-1])

重點在最後兩個判斷條件, 當i的值與i-1的值相同, 且i-1沒被使用過, 這種情況只會發生在組合(i-1, i)已經被計算過, 並且現在的組合為(i, i-1), 此時可以很明顯的看出現在的組合已經出現過了, 所以必須跳過這輪。

同理, 若i-1已被使用過, 那此時的組合為(u-1, i), 由於順序問題, 可以判斷出這是該組合的第一次出現, 因此不需要跳過。

---

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<int> used(nums.size(), 0);
        vector<int> tmp;
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        dfs(nums, tmp, used, ans);
        return ans;
    }
    void dfs(vector<int>& nums, vector<int>& tmp, vector<int>& used, vector<vector<int>>& ans){
        if(tmp.size()==nums.size()){
            ans.emplace_back(tmp);
            return;
        }
        for(int i=0;i<nums.size();i++){
            if(used[i]||(i>0 && nums[i]==nums[i-1] && !used[i-1]))continue;
            used[i]=1;
            tmp.push_back(nums[i]);
            dfs(nums, tmp, used, ans);
            tmp.pop_back();
            used[i]=0;
        }
    }
};