[leetcode]Permutations II

新博文地址：[leetcode]PermutationsII

Permutations II

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].

 排列的题应该是很熟悉的，不熟悉的可以看这几道题：Permutations，Next Permutation, 其实，求排列的算法大致一样，这不过这道题要求可以有重复数字，求唯一的排列组合。

说起唯一，自然想起Set，我的算法也完全依赖于set，即，在生成排列序列的时候，先检查一下是否已经存在了，如果存在就不需要返回了。set的key很自然的选择用数组的String表达，遗憾的是，空间复杂度略大......

 

 

 private String getString(List<Integer> list){
	StringBuilder sb = new StringBuilder();
		for(int i : list){
			sb.append(i);
		}
		return sb.toString();
	}
	public List<List<Integer>> permuteUnique(int[] num) {
		Set<String> set = new HashSet<String>();
		List<List<Integer>> result = new ArrayList<List<Integer>>();
		if (num == null || num.length == 0) {
			return result;
		}
		if (num.length == 1) {
			List<Integer> list = new ArrayList<Integer>();
			list.add(num[0]);
			result.add(list);
			return result;
		}
		int[] pre = Arrays.copyOf(num, num.length - 1);
		List<List<Integer>> prePer = permuteUnique(pre);
		for (List<Integer> list : prePer) {
			for (int i = 0; i <= list.size(); i++) {
				List<Integer> newList = new ArrayList<Integer>();
				for(int j = 0; j < i ;j ++){
					newList.add(list.get(j));
				}
				newList.add(num[num.length - 1]);
				for(int j = i; j < list.size(); j++){
					newList.add(list.get(j));
				}
				if(!set.contains(getString(newList))){
					set.add(getString(newList));
					result.add(newList);
				}
			}
		}
		return result;
	}