Last updated on January 19th, 2025 at 05:58 pm

Here, we see a Subsets II LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Array, Backtracking

Companies

Facebook

Level of Question

Medium

Subsets II LeetCode Solution

1. 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]]

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is Subsets. This pattern is commonly used to solve problems where we need to generate all possible subsets (or combinations) of a given set of elements, including handling duplicates.

3. Code Implementation in Different Languages

3.1 Subsets II 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;
    }
};

3.2 Subsets II 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.3 Subsets II 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;    
};

3.4 Subsets II 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

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(2n)	O(2n)
Java	O(2n)	O(2n)
JavaScript	O(2n)	O(2n)
Python	O(2n)	O(2n)

• The Subsets pattern is used to generate all possible subsets of a given array.
• Sorting the array helps in efficiently handling duplicates.
• The time and space complexity for all implementations is O(2ⁿ), which is expected for subset generation problems.