Blogs Hub

by Sumit Chourasia | Nov 17, 2020 | Category :coding | Tags : algorithm array data-structure leetcode medium

Subsets II - Array - Medium - LeetCode

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)