Print Permutations of an array with duplicate elements

preview_player
Показать описание
Given an array with duplicate elements. Print all the unique permutations of elements of the array. In part-1 of this problem we discussed the solution where there are no duplicates in the array.

Covers Following Leetcode Problems:
-----------------------------------------------------
Join our 30-days online course to prepare for coding interviews of companies like Google, Amazon, Facebook, Microsoft, etc.

We have our office in Greater Noida (India) where we run courses for students to prepare them for placements in Top IT companies. For Placement Preparation and Industrial Training call us.

Call: +91-8377803450

Call us to conduct a workshop in your college campus.

Buy our books and prepare for coding interviews on your own.

For detailed discussions on Interview Questions visit:
Рекомендации по теме
Комментарии
Автор

loved it sir!
hash map solution is so easy

prateekrajput
Автор

Nice video. However, I still haven't understood which part of the logic prevent the printing 122, 122. 1 is the only non-repeating element. But after fixing that 1 you are left with the subset {2, 2} and this subset is then permuted. Shouldn't there be a condition/contrain on that subset to prevent the same permutation being printed twice?.
Your logic, to my understanding, only goes to show how to avoid fixing a duplicate element in a given set more than once. Hence compressing the output: 212, 221 and 221, 212 into just 212 and 221.

mk-xq
Автор

Sir how to show 100 ^ 50 permutation list, plz answer me

mrinaldas
Автор

what's the space complexity of this approach? Will it be O(N) or O(N*N) as the recursion goes deep till n and at each level we could have a HashSet of size N.

KishoreKumar-pfku
Автор

Getting wrong answer

public class Solution {
ArrayList<ArrayList<Integer>> ans = new

public int[][] permute(int[] A) {

ArrayList<Integer> a = new ArrayList();

for(int i=0; i<A.length; i++)
a.add(A[i]);
//this.A = A;
f(a, 0);

int rows = ans.size();
int cols = 0;

if(rows > 0)
cols = ans.get(0).size();



int[][] r = new int[rows][cols];


for(int i=0; i<rows; i++){
ArrayList<Integer> row = ans.get(i);
for(int j=0; j< cols; j++){
r[i][j] = row.get(j);
}
}



return r;



}

void f(ArrayList<Integer> A, int pos){

if(pos==A.size()-1)
ans.add(A);

HashSet<Integer> hs = new HashSet();

for(int i=pos; i<A.size(); i++){
if(hs.contains(A.get(i)) == true)
continue;

hs.add(A.get(i));

Collections.swap(A, i, pos);

f(A, pos+1);

Collections.swap(A, i, pos);
}


}
}

dipikakale