Subsets II [C++]
IntuitionThe problem asks us to find all subsets of a given list of integers where some integers may be duplicated. The main challenge is to ensure that we don'
# Intuition
The problem asks us to find all subsets of a given list of integers where some integers may be duplicated. The main challenge is to ensure that we don't generate the same subset more than once.

# Approach
We can use backtracking to generate subsets while ensuring that duplicates are not included. Here's how we can do that:
1. **Sorting**: First, we sort the input list. This helps to group duplicate elements together, which will allow us to easily skip over them in the recursive function.
2. **Backtracking**: Start with an empty subset and build subsets step by step by including or excluding each number. For each number, if it is the same as the previous one, we skip it to avoid generating the same subset multiple times.
3. **Base case**: We always add the current subset to the result, even if it's empty.

# Complexity
- **Time complexity**: $$O(2^n)$$, where \( n \) is the number of elements in the input list. In the worst case, we generate all possible subsets. The sorting step takes $$O(n \log n)$$, but the subset generation itself dominates, hence the overall complexity is $$O(2^n)$$.
  
- **Space complexity**: $$O(n)$$ for the recursive call stack and the space used to store subsets in the result.

# Code
```cpp
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> current;
        sort(nums.begin(), nums.end());
        backtrack(nums, 0, current, result);
        return result;
    }

    void backtrack(vector<int>& nums, int index, vector<int>& current, vector<vector<int>>& result) {
        result.push_back(current);
        for (int i = index; i < nums.size(); ++i) {
            if (i > index && nums[i] == nums[i - 1]) continue;
            current.push_back(nums[i]);
            backtrack(nums, i + 1, current, result);
            current.pop_back();
        }
    }
};
```
['C++']