LeetCode Link: 47. Permutations II
Language: C#
Problem Statement
Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.
Example 1:
Input: nums = [1,1,2]
Output:
[[1,1,2],
[1,2,1],
[2,1,1]]
Example 2:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Constraints:
- 1 <= nums.length <= 8
- -10 <= nums[i] <= 10
Solution
public class Solution {
HashSet<string> unique = new();
public IList<IList<int>> PermuteUnique(int[] nums) {
var list = new List<IList<int>>();
BT(list, new(), nums, new());
return list;
}
private void BT(IList<IList<int>> list, List<int> temp, int[] nums, HashSet<int> set)
{
var n = nums.Length;
if (temp.Count == n)
{
var l = new List<int>(temp);
list.Add(l);
}
for (int i=0; i<n; i++)
{
if (set.Contains(i))
{
continue;
}
set.Add(i);
temp.Add(nums[i]);
var s = string.Concat(temp);
if (temp.Count != n || !unique.Contains(s))
{
if(temp.Count == n)
{
unique.Add(s);
}
BT(list, temp, nums, set);
}
temp.RemoveAt(temp.Count - 1);
set.Remove(i);
}
}
}