Subsets II - Array - Medium - LeetCode

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

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

public class Solution {
 IList<IList<int>> result = new List<IList<int>>();
 HashSet<string> set = new HashSet<string>();
 public IList<IList<int>> SubsetsWithDup(int[] nums) {
 var map = new Dictionary<int,int>();
 Array.Sort(nums);
 for(int i=0;i<nums.Length;i++){
 if(map.ContainsKey(nums[i])){
 map[nums[i]]++;
 }
 else{
 map.Add(nums[i],1);
 }
 }
 
 var list = new List<int>();
 
 Helper(nums, map, list);
 
 return result;
 }
 
 private void Helper(int[] nums, Dictionary<int,int> map, List<int> list){
 if(list.Count() > nums.Length){
 return;
 }
 
 AddToResult(list);
 
 var temp = new List<int>(map.Keys); 
 foreach(var item in temp){
 
 if(list.Count()>0 && item<list[list.Count()-1]){
 continue;
 }
 
 if(map[item] > 0){
 list.Add(item);
 map[item]--;
 Helper(nums, map, list);
 list.RemoveAt(list.Count()-1);
 map[item]++;
 }
 }
 }
 
 private void AddToResult(List<int> list){ 
 var temp = new List<int>(list);
 result.Add(temp);
 }
}

Time Complexity: O(2^n)

Space Complexity: O(n)