Subsets II Problem Solution [Leetcode]

Subsets II Problem: Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example :

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

Subsets II Problem Solution [Leetcode]

Problem Solution In Python

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        ret = set()
        def fn(start, l, tmp):
            if len(tmp) == l:
                ret.add(tuple(tmp))
                return
            
            for i in range(start, len(nums)):
                if i>start and nums[i] == nums[i-1]: continue
                fn(i+1, l, tmp+[nums[i]])
                
        
        for length in range(len(nums)+1):
            fn(0,length,[])
            
        return ret

Problem Solution In Java

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] num) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        result.add(new ArrayList());
        
        Arrays.sort(num);
        
        for(int i : num){
            List<List<Integer>> temp = new ArrayList<List<Integer>>();
            for(List<Integer> sub : result){
                List<Integer> inner = new ArrayList<Integer>(sub);
                inner.add(i);
                if(!result.contains(inner))
                    temp.add(inner);
            }
            result.addAll(temp);
        }
        return result;
    }
}

Problem Solution In C++

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        
        set<multiset<int>> st;
        
        vector<vector<int>> res;
        
        multiset<int> s;
        
        dfs(st,s, nums, 0);
        
        for(auto x: st){
            res.push_back(vector<int> (x.begin(),x.end()));
        }
        
        return res;
    }
    
    void dfs(set<multiset<int>>& st, multiset<int> s, vector<int> nums, int i){
        
        st.insert(s);
        
        if(i>=nums.size())
            return;
        
        dfs(st,s,nums,i+1);
        
        s.insert(nums[i]);
        
        dfs(st,s,nums,i+1);
        
        
    }
};

Problem Solution In C

void helper(int* nums, int len, int* rsize, int* *rcsizes, int** *ans, int ptr, int _len) {
    if (_len >= len || ptr >= len) return;  

    int prev = *rsize - 1;

    for (int q = ptr; q < len; q++){ 
        if (q > ptr && nums[q] == nums[q-1]) continue;
        (*rcsizes)[*rsize] = _len + 1;
        (*ans)[*rsize] = malloc(sizeof(int) * (*rcsizes)[*rsize]);
        memcpy((*ans)[*rsize], (*ans)[prev], sizeof(int) *_len); 
        (*ans)[*rsize][_len] = nums[q]; 

        (*rsize)++; 

        helper(nums, len, rsize, rcsizes, ans, q + 1, _len + 1); 
    } 
}

int cmp (int *a, int *b){
    return *a - *b;
}

int** subsetsWithDup(int* nums, int len, int* rsize, int* *rcsizes){
	
    qsort(nums, len, sizeof(int), cmp);
    
    *rcsizes = malloc(sizeof(int) * pow(2, len));
    (*rcsizes)[0] = 0;
    
    int* *ans = malloc(sizeof(int*) * pow(2, len));
    
    *rsize = 1; 

    helper(nums, len, rsize, rcsizes, &ans, 0, 0); 

    return ans;
}