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

https://oj.leetcode.com/problems/permutations-ii/

思路：有重复元素的数组生成permutation，要去除掉重复的情况：先排序，然后还是permutation的思路，依次往cur位置填元素，因为有些元素有多次，所以需要用c1,c2来统计已经填好的数量和总共需要填的数量，并且因为排序了，相同元素的去重只需要跟前一个元素比较一下是否相等 （if (i == 0 || num[i] != num[i - 1])）。

import java.util.ArrayList;import java.util.Arrays;public class Solution {	public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {		if (num == null)			return null;		ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();		if (num.length == 0)			return res;		Arrays.sort(num);		int[] permSeq = new int[num.length];		perm(num.length, 0, num, permSeq, res);		return res;	}	private void perm(int n, int cur, int[] num, int[] perm,			ArrayList<ArrayList<Integer>> res) {		if (cur == n) {			ArrayList<Integer> tmp = new ArrayList<Integer>();			for (int i = 0; i < perm.length; i++) {				tmp.add(perm[i]);			}			res.add(tmp);		} else {			int i;			for (i = 0; i < num.length; i++)				// this "if" is the key part				if (i == 0 || num[i] != num[i - 1]) {					int j;					int c1 = 0, c2 = 0;					for (j = 0; j < num.length; j++) {						if (num[i] == num[j])							c1++;					}					for (j = cur - 1; j >= 0; j--) {						if (perm[j] == num[i])							c2++;					}					if (c2 < c1) {						perm[cur] = num[i];						perm(n, cur + 1, num, perm, res);					}				}		}	}	public static void main(String[] args) {		System.out.println(new Solution().permuteUnique(new int[] { -1, 2, -1,				2, 1, -1, 2, 1 }));	}}