题目描述：
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].
对一个数组生成全排列。
与Permutation 1几乎一模一样：
https://leetcode.com/problems/permutations/
唯一不同在于需要去除重复的序列。
思路：
与Permutation 1 不同，本题采用Heap Permutation的解法来生成全排列。
具体参考：
https://en.wikipedia.org/wiki/Heap%27s_algorithm
实现代码：public class Solution {
public IList<IList<int>> PermuteUnique(int[] nums)
{
var n = nums.Length ;
var lst = new List<int>(nums);
var dict = new Dictionary<string, IList<int>>();
HeapPermute(ref lst, n, ref dict);
return dict.Values.ToList();
}
private void HeapPermute(ref List<int> nums, int n, ref Dictionary<string, IList<int>> result)
{
if (n == 1) {
var k = K(nums);
if(!result.ContainsKey(k)){
result.Add(k , new List<int>(nums));
}
}
else {
for (int i = 0; i < n - 1; i++)
{
HeapPermute(ref nums, n-1, ref result);
if (n % 2 == 1){
Swap(ref nums, 0, n-1);
}
else{
Swap(ref nums, i, n-1);
}
}
HeapPermute(ref nums, n-1, ref result);
}
}
private void Swap(ref List<int> nums, int i ,int j)
{
var t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
private string K(IList<int> nums)
{
return string.Join(",", nums);
}
}