algoadvance

Leetcode 90. Subsets II

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.

Clarifying Questions

1. Input Constraints:
   • What is the maximum length of the nums array?
   • Is the input array always going to be non-empty?
2. Output Format:
   • Should the subsets be returned in any particular order?
   • What should be returned if nums is empty?

Assuming the answers are:

• The length of the nums array will be bounded, say up to 10^4.
• The input array can be empty.
• The order of subsets in the output does not matter, and if nums is empty, return [[]].

Strategy

1. Sorting:
   • First, sort the nums array to handle duplicates easily.
2. Backtracking:
   • Use a backtracking approach to generate subsets.
   • As we process each element, we decide whether to include it in the current subset or not.
   • To handle duplicates, if the current number is the same as the previous number, we skip the inclusion of this number to avoid duplicate subsets.

Code

Here is the C++ code to solve the problem:

#include <vector>
#include <algorithm>

class Solution {
public:
    void backtrack(int start, std::vector<int>& nums, std::vector<int>& current, std::vector<std::vector<int>>& result) {
        result.push_back(current);
        for (int i = start; i < nums.size(); ++i) {
            if (i > start && nums[i] == nums[i - 1]) continue;  // Skip duplicates
            current.push_back(nums[i]);
            backtrack(i + 1, nums, current, result);
            current.pop_back();
        }
    }

    std::vector<std::vector<int>> subsetsWithDup(std::vector<int>& nums) {
        std::sort(nums.begin(), nums.end());  // Sort to handle duplicates
        std::vector<std::vector<int>> result;
        std::vector<int> current;
        backtrack(0, nums, current, result);
        return result;
    }
};

Time Complexity

• Sorting: O(n log n), where n is the size of the nums array.
• Backtracking: Each element has two choices (include or not include), leading to 2^n possible subsets in the worst case. For each subset, generating a copy of the subset takes O(n) time. Thus, the complexity for generating all subsets can be approximated as O(n * 2^n).

Therefore, the overall time complexity is O(n log n) + O(n * 2^n) ≈ O(n * 2^n).

This approach ensures that we handle duplicates correctly and generates all unique subsets efficiently.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?