[Microsoft][LeetCode] Permutations II

Problem: Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Example:

Input: nums = [1,1,2]
Output:
[[1,1,2],
 [1,2,1],
 [2,1,1]]

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Approach: This is same question as print permutation of a string but here the input contains duplicates. We are just going to use the same approach of backtracking which we used in the above question but while adding the current permutation to result, we will just check for duplicate. We can use HashSet for it.

Implementation in C#:

    public IList<IList<int>> PermuteUnique(int[] nums)

    {

        List<IList<int>> result = new List<IList<int>>();

        Array.Sort(nums);

        this.PermuteUnique(nums, 0, result, new HashSet<string>());

        return result;

    }

    private void PermuteUnique(int[] nums,

                            int index,

                            IList<IList<int>> result,

                            HashSet<string> set)

    {

        if (index == nums.Length)

        {

            string key = this.GetKey(nums);

            if (set.Add(key))

            {

                result.Add(nums.ToList());

            }

            return;

        }

        for (int j = index; j < nums.Length; ++j)

        {

            this.Swap(nums, index, j);

            this.PermuteUnique(nums, index + 1, result, set);

            this.Swap(nums, index, j);

        }

    }

    private string GetKey(int[] nums)

    {

        return string.Join("-", nums);

    }

    private void Swap(int[] nums, int i, int j)

    {

        int temp = nums[i];

        nums[i] = nums[j];

        nums[j] = temp;

    }

Complexity: O(n * !n)