SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

This function generates all possible subsets of a given list of integers, ensuring that no duplicate subsets are included. The input list may contain duplicates, and the solution accounts for this by sorting the list first and then using a recursive approach to build the subsets.

Intuition

The key to avoiding duplicate subsets lies in sorting the input list. By processing duplicates together, the algorithm can skip over redundant elements after including them in a subset. This ensures that each subset is unique, even when the input contains repeated numbers.

Approach

1. Sort the Input List: Begin by sorting the list of integers to ensure that duplicates are adjacent. This helps in easily skipping over duplicates during subset generation.

2. Recursive Backtracking: Use a recursive function to explore all possible subsets:

   • Start from the first element and consider including it in the current subset.
   • Recursively move to the next element.
   • After exploring the inclusion of the current element, backtrack by removing it from the subset.
   • Skip over any duplicate elements to prevent generating the same subset multiple times.

3. Base Case: The recursion ends when the index exceeds the length of the list, at which point the current subset is added to the result.

Complexity

Time Complexity:

The time complexity is (O(2^n)), where (n) is the number of elements in the input list. This is because the algorithm explores all possible subsets.

Space Complexity:

The space complexity is (O(n)) due to the recursive stack and the space required to store each subset.

Code

C++

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> ans;
        vector<int> set;
        sort(nums.begin(), nums.end());
        
        function<void(int)> subset = [&](int idx) {
            if (idx >= n) {
                ans.push_back(set);
                return;
            }
            
            set.push_back(nums[idx]);
            subset(idx + 1);
            set.pop_back();
            
            while (idx + 1 < n && nums[idx] == nums[idx + 1]) {
                idx++;
            }
            subset(idx + 1);
        };
        
        subset(0);
        return ans;
    }
};

Python

class Solution:
    def subsetsWithDup(self, nums):
        n = len(nums)
        ans = []
        current_set = []
        nums.sort()

        def subset(idx):
            if idx >= n:
                ans.append(current_set[:])
                return
            
            current_set.append(nums[idx])
            subset(idx + 1)
            current_set.pop()
            
            while idx + 1 < n and nums[idx] == nums[idx + 1]:
                idx += 1
            
            subset(idx + 1)
        
        subset(0)
        return ans

Java

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        int n = nums.length;
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> set = new ArrayList<>();
        Arrays.sort(nums);
        
        backtrack(nums, n, ans, set, 0);
        return ans;
    }
    
    private void backtrack(int[] nums, int n, List<List<Integer>> ans, List<Integer> set, int idx) {
        if (idx >= n) {
            ans.add(new ArrayList<>(set));
            return;
        }
        
        set.add(nums[idx]);
        backtrack(nums, n, ans, set, idx + 1);
        set.remove(set.size() - 1);
        
        while (idx + 1 < n && nums[idx] == nums[idx + 1]) {
            idx++;
        }
        backtrack(nums, n, ans, set, idx + 1);
    }
}

JavaScript

var subsetsWithDup = function (nums) {

    let n = nums.length;
    let ans = [];
    let set = [];
    nums.sort((a, b) => a - b);
    function subset(idx) {
        if (idx >= n) {
            ans.push([...set]);
            return;
        }
        set.push(nums[idx]);
        subset(idx + 1);
        set.pop();
        while (idx + 1 < n && nums[idx] == nums[idx + 1]) {
            idx = idx + 1
        };
        subset(idx + 1);

    }
    subset(0);
    return ans;
};