Subsets II LeetCode Solution

Last updated on October 10th, 2024 at 12:07 am

Here, We see Subsets II LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

Array, Backtracking

Companies

Facebook

Level of Question

Medium

Subsets II LeetCode Solution

Subsets II LeetCode Solution

Problem Statement

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 1:

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

Example 2:

Input: nums = [0]
Output: [[],[0]]

1. Subsets II Leetcode Solution C++

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int> > totalset = {{}};
        sort(nums.begin(),nums.end());
        for(int i=0; i<nums.size();){
            int count = 0; // num of elements are the same
            while(count + i<nums.size() && nums[count+i]==nums[i])  count++;
            int previousN = totalset.size();
            for(int k=0; k<previousN; k++){
                vector<int> instance = totalset[k];
                for(int j=0; j<count; j++){
                    instance.push_back(nums[i]);
                    totalset.push_back(instance);
                }
            }
            i += count;
        }
        return totalset;
    }
};

2. Subsets II Leetcode Solution Java

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> each = new ArrayList<>();
    helper(res, each, 0, nums);
    return res;
}
public void helper(List<List<Integer>> res, List<Integer> each, int pos, int[] n) {
    if (pos <= n.length) {
        res.add(each);
    }
    int i = pos;
    while (i < n.length) {
        each.add(n[i]);
        helper(res, new ArrayList<>(each), i + 1, n);
        each.remove(each.size() - 1);
        i++;
        while (i < n.length && n[i] == n[i - 1]) {i++;}
    }
    return;       
    }
}

3. Subsets II Leetcode Solution JavaScript

var subsetsWithDup = function(nums) {
    nums = nums.sort((a,b) => a-b);
    const res = [];
    function fn(length, start=0, arr = []) {
        if (arr.length === length) {
            res.push(arr.slice());
            return;
        }
        for(let i=start; i<nums.length; i++) {       
            if (i !== start && nums[i-1] === nums[i]) continue;
            arr.push(nums[i]);
            fn(length, i+1, arr);
            arr.pop();            
        }
    }
    for(let length=0; length<=nums.length; length++) {
        fn(length);
    }
    return res;    
};

4. Subsets II Leetcode Solution Python

class Solution(object):
    def subsetsWithDup(self, nums):
        res = [[]]
        nums.sort()
        for i in range(len(nums)):
            if i == 0 or nums[i] != nums[i - 1]:
                l = len(res)
            for j in range(len(res) - l, len(res)):
                res.append(res[j] + [nums[i]])
        return res
Scroll to Top