Permutations II (Java)

LeetCode

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

For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

	Given a collection of numbers that might contain duplicates, return all possible unique permutations.
	For example,
	[1,1,2] have the following unique permutations:
	[1,1,2], [1,2,1], and [2,1,1].
	Time complexity O(n!);
	import java.util.*;
	public class PermutationII {
	public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (num==null){
	return null;
	}
	ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
	if (num.length==0){
	return result;
	}
	// Hashtable<ArrayList<Integer>, Boolean> ht=new Hashtable<ArrayList<Integer>, Boolean>();
	ArrayList<Integer> temp=new ArrayList<Integer>();
	temp.add(num[0]);
	result.add(temp);
	for (int i=1; i<num.length; i++){
	result=insert(num[i], result);
	}
	return result;
	}
	private ArrayList<ArrayList<Integer>> insert(int i, ArrayList<ArrayList<Integer>> result){
	ArrayList<ArrayList<Integer>> newResult=new ArrayList<ArrayList<Integer>>();
	Hashtable<ArrayList<Integer>, Boolean> ht=new Hashtable<ArrayList<Integer>, Boolean>();
	for (ArrayList<Integer> current: result){
	for (int j=0; j<=current.size(); j++){
	ArrayList<Integer> temp=new ArrayList<Integer>();
	temp.addAll(current);
	temp.add(j, i);
	if (!ht.containsKey(temp)){
	newResult.add(temp);
	ht.put(temp, true);
	}
	}
	}
	return newResult;
	}
	}

view raw PermutationII.java hosted with ❤ by GitHub