# 47 - Permutation II

解法一 - Backtracking

這題跟 # 46 - Permutation 的做法有一個很大差別，主要就是因為會有重複的元素，所以我們要排列的不是 nums[i]，而是 i。但因為有些 element 可能重複，所以如果列舉出所有可能的 index 排列，就一定會有數值上重複的排列。

為了避免列舉到數值重複的 index 排列，我們做了兩件事：

1. 先把 nums sort 過一遍

2. 在繼續呼叫 helper 之前，除了要先檢查當前 index 還在 state 裡，還要看看前一個 element 是否重複，而且如果前一個 element 跟現在重複，而且前一個 element 的 index 還在 state 中，就表示這次的 permutation 不能用，因為以當前 element 開頭會跟用前一個element 開頭長得一模一樣。

實作如下：

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> sol;
        if(nums.empty()) return sol;

        set<int> state;
        for(int i=0; i<nums.size(); i++)
            state.insert(i);

        vector<int> tmp;

        sort(nums.begin(), nums.end());
        helper(nums, sol, state, tmp);

        return sol;
    }

private:
    void helper(vector<int>& nums, vector<vector<int>>& sol, set<int>& state, vector<int>& tmp)     {
        if(state.empty())
            sol.push_back(tmp);
        else {
            for(int i=0; i<nums.size(); i++) {
                if(state.find(i) == state.end()) continue;

                // (state.find(i-1) != state.end())==false is important!!!
                // this means current permutation starts at i
                // but since nums[i-1] == nums[i], we already have a permutation
                // starts at i-1, with value == nums[i-1]
                // So we don't want to keep going with permutation starts at i
                if(i>0 && nums[i-1]==nums[i] && (state.find(i-1) != state.end())==false ) continue;
                else {
                    state.erase(state.find(i));
                    tmp.push_back(nums[i]);
                    helper(nums, sol, state, tmp);
                    state.insert(i);
                    tmp.pop_back();
                }
            }
        }
    }
};