Permutations II

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

Example:

Input:  nums={1,1,2}
Output: res=[[1,1,2],[1,2,1],[2,1,1]]

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;
public class PermutationsII {
    public static void main(String[] args) {
        int nums[] = { 2, 2, 1, 1 };
        List<List<Integer>> res = permuteUnique(nums);
        System.out.println(Arrays.asList(res));
    }
    static List<List<Integer>> ans;
    static void generate(int l, int r, List<Integer> nums) {
        if (l == r) {
            if (!ans.contains(nums)) {
                List<Integer> list = new ArrayList<Integer>();
                list.addAll(nums);
                ans.add(list);
            }
        } else {
            for (int i = l; i <= r; i++) {
                Collections.swap(nums, l, i);
                generate(l + 1, r, nums);
                Collections.swap(nums,l, i);
            }
        }
    }
    static List<List<Integer>> permuteUnique(int[] nums) {
        int n = nums.length;
        ans = new ArrayList<List<Integer>>();
        generate(0, n - 1, Arrays.stream(nums).boxed().
                collect(Collectors.toList()));
        return ans;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
set<vector<int>> st1;
vector<vector<int>> ans;
    void generate(int l,int r,vector<int> &nums)
    {
        if(l==r)
        {
            if(st1.find(nums)==st1.end())
            {
                ans.push_back(nums);
                st1.insert(nums);
            }
        }
        else
        {
            for(int i=l;i<=r;i++)
            {
                swap(nums[l],nums[i]);
                generate(l+1,r,nums);
                swap(nums[l],nums[i]);
            }
        }
    }
vector<vector<int>> permuteUnique(vector<int>& nums) 
{
        int n=nums.size();
        ans.clear();
        st1.clear();
        generate(0,n-1,nums);
        return ans;
}
int main()
{
    vector<int> nums={1,1,2};
    vector<vector<int>> res=permuteUnique(nums);
    cout<<"[";
    for(int i=0;i<res.size();i++)
     {
         cout<<"[";
         for(int j=0;j<res[i].size();j++)
           {
               cout<<res[i][j];
               if(j!=res[i].size()-1)
                  cout<<",";
           }
           cout<<"]";
           if(i!=res.size()-1)
             cout<<",";
     }
    cout<<"]";
}