class Solution {
public:
    /**
     * @param nums: A list of integers.
     * @return: A list of unique permutations.
     */
    vector<vector<int> > permuteUnique(vector<int> &nums) {
        // write your code here
        sort(nums.begin(), nums.end());
        vector<vector<int>> results;
        vector<bool> visited(nums.size(), false);
        vector<int> soFar;
        findAllPermutations(nums, soFar, visited, results);
        return results;
    }
    // The key observation is that since there are duplicates in array nums, after sorting and all duplicates are aggregated as neighbors, we need to move the block of same numbers together! To do it in code, we need to ensure that when nums[i - 1] == nums[i], we can only insert nums[i] into the soFar array WHEN nums[i - 1] HAS BEEN INSERTED ALREADY! so that we ensure that when we move the blocks of same numbers, the internal sequence of the elements in the block has been preserved;
    void findAllPermutations(vector<int> &nums, vector<int>& soFar, vector<bool>& visited, vector<vector<int>>& results) {
        if (soFar.size() == nums.size()) {
            results.push_back(soFar);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            if (visited[i]) {
                continue;
            }
            if (i != 0 && nums[i - 1] == nums[i] && !visited[i - 1]) {
                continue;
            }
            visited[i] = true;
            soFar.push_back(nums[i]);
            findAllPermutations(nums, soFar, visited, results);
            visited[i] = false;
            soFar.pop_back();
        }

        return;
    }
};