Permutation II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

Input: [1,1,2] Output: [ [1,1,2], [1,2,1], [2,1,1] ]

Solution: Backtracking

To prevent duplicate solution, we sort the input array first. Then for every state, we check if the current number is equal to previous number.

We use the number only when the previous equal element has been visited before.

void backtrack(vector<int> &arr, vector<bool> &visited, vector<int> &nums, vector<vector<int>> &ans) {
    if (arr.size() == nums.size()) {
        ans.push_back(arr);
        return;
    }

    for (int i=0; i<nums.size(); i++) {
        if (visited[i]) continue;
        if (i > 0 && nums[i] == nums[i-1] && visited[i-1] == false) continue;
        visited[i] = true;
        arr.push_back(nums[i]);
        backtrack(arr, visited, nums, ans);
        arr.pop_back();
        visited[i] = false;
    }
}

vector<vector<int>> permuteUnique(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<bool> visited(nums.size(), false);
    vector<int> arr;
    vector<vector<int>> ans;
    backtrack(arr, visited, nums, ans);
    return ans;
}

Solution: Using swapping and set

If the two elements are the same, then we don't need to swap them. But we also need to use set to ensure the uniqueness.

O(log(n)) for set insert operation.

void permute(vector<int> &nums, int start, set<vector<int>> &res) {
    if (start >= nums.size()) res.insert(nums);
    for (int i = start; i < nums.size(); ++i) {
        if (i != start && nums[i] == nums[start]) continue;
        swap(nums[i], nums[start]);
        permute(nums, start + 1, res);
        swap(nums[i], nums[start]);
    }
}

vector<vector<int>> permuteUnique(vector<int>& nums) {
    set<vector<int>> res;
    permute(nums, 0, res);
    return vector<vector<int>> (res.begin(), res.end());
}