8. Permutations II

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

Example 1:

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

Example 2:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Solution: (Backtracking with set)

class Solution
{
public:
    set<vector<int>> st;
    
    void permute(vector<int> &nums, int pos, int n)
    {
        if (pos >= n)
        {
            st.insert(nums);
            return;
        }

        for (int i = pos; i < nums.size(); i++)
        {
            swap(nums[pos], nums[i]);
            permute(nums, pos + 1, n);
            swap(nums[pos], nums[i]);
        }

        return;
    }

    vector<vector<int>> permuteUnique(vector<int> &nums)
    {
        vector<vector<int>> res;
        permute(nums, 0, nums.size());
        
        for (auto itr = st.begin(); itr != st.end(); itr++)
        {
            res.push_back(*itr);
        }

        return res;
    }
};

Solution: (Backtracking with same array)

class Solution
{
public:
    vector<vector<int>> res;
    
    void permute(vector<int> nums, int pos, int n)
    {
        if (pos >= n)
        {
            res.push_back(nums);
            return;
        }

        for (int i = pos; i < nums.size(); i++)
        {
            if(i>pos && nums[pos] == nums[i]){
                continue;
            }
            
            swap(nums[pos], nums[i]);
            permute(nums, pos + 1, n);

        }

        return;
    }

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