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
        vector<vector<int> > results;
        if (nums.size() == 0) {
            results.push_back(vector<int>());
            return results;
        }

        sort(nums.begin(), nums.end()); // sort will aggregate duplicate numbers;
        vector<bool> visited(nums.size(), false);
        vector<int> current;

        dfsHelper(nums, current, visited, results);

        return results;
    }
    // 1. definition: get a permutation of numbers from nums that have not been visited before and put them into current;
    void dfsHelper(vector<int> &nums, vector<int>& current, vector<bool>& visited, vector<vector<int> >& results) {
        if (nums.size() == current.size()) {
            results.push_back(current);
            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;
            }
            current.push_back(nums[i]);
            visited[i] = true;
            dfsHelper(nums, current, visited, results);
            current.pop_back();
            visited[i] = false;
        }
    }
};