Subsets With Duplicates? No Sweat, Just Skip the Clones! || Easy solution with simple explaination.
1. Intuition"Generate all possible subsets, but dodge duplicates like they’re your ex at a party."
The idea is simple: we’re building subsets by either includin
## 1. Intuition
*"Generate all possible subsets, but dodge duplicates like they’re your ex at a party."*  
The idea is simple: we’re building subsets by either including or excluding each number, but since duplicates exist, we skip over identical numbers when excluding to avoid déjà vu in our results.

## 2. Approach
- **Sort First**: Sort the input array so duplicates are neighbors—easier to spot and skip.
- **Recursive Magic**: Use a helper function `generateSubset` that:
  - Takes an index (`idx`), the input array (`nums`), a current subset (`ans`), and the final solution list (`sol`).
  - Base case: If we’ve processed all elements, add the current subset to the solution.
  - Two choices at each step:
    - *Include* the current number and recurse.
    - *Exclude* it, skip all duplicates of it, and recurse.
- **Backtracking**: After including a number, pop it off to explore the exclude path.
- **Sarcasm Alert**: Duplicates? We don’t have time for their drama—skip ‘em like a bad sequel.

## 3. Step-by-Step Dry Run
Let’s take `nums = [1, 2, 2]` and see this bad boy in action. Assume it’s sorted (it is, thanks to `sort(nums.begin(), nums.end())`).

- **Initial Call**: `idx = 0`, `ans = []`, `sol = []`
  - **Include 1**: `ans = [1]`, recurse to `idx = 1`
    - **Include 2**: `ans = [1, 2]`, recurse to `idx = 2`
      - **Include 2**: `ans = [1, 2, 2]`, recurse to `idx = 3`
        - Base case: `sol = [[1, 2, 2]]`
      - **Exclude 2**: Pop `2`, `ans = [1, 2]`, skip duplicates (next is 2, skip to `idx = 3`)
        - Base case: `sol = [[1, 2, 2], [1, 2]]`
    - **Exclude 2**: Pop `2`, `ans = [1]`, skip duplicates (next is 2, skip to `idx = 2`)
      - **Include 2**: `ans = [1, 2]`, recurse to `idx = 3`
        - Base case: `sol = [[1, 2, 2], [1, 2], [1, 2]]` (Oops, duplicate avoided earlier!)
      - **Exclude 2**: Pop `2`, `ans = [1]`, recurse to `idx = 3`
        - Base case: `sol = [[1, 2, 2], [1, 2], [1]]`
  - **Exclude 1**: Pop `1`, `ans = []`, recurse to `idx = 1`
    - **Include 2**: `ans = [2]`, recurse to `idx = 2`
      - **Include 2**: `ans = [2, 2]`, recurse to `idx = 3`
        - Base case: `sol = [[1, 2, 2], [1, 2], [1], [2, 2]]`
      - **Exclude 2**: Pop `2`, `ans = [2]`, skip to `idx = 3`
        - Base case: `sol = [[1, 2, 2], [1, 2], [1], [2, 2], [2]]`
    - **Exclude 2**: Pop `2`, `ans = []`, skip duplicates to `idx = 3`
      - Base case: `sol = [[1, 2, 2], [1, 2], [1], [2, 2], [2], []]`

**Final Output**: `[[], [2], [2, 2], [1], [1, 2], [1, 2, 2]]`  
*Note*: The while loop ensures we don’t get `[1, 2]` twice—genius, right?

## 4. Time and Space Complexity Analysis
- **Time Complexity**: O(2^n)  
  - Each element can either be in or out (2 choices), and we have `n` elements. Sorting takes O(n log n), but the recursive subset generation dominates with O(2^n). Skipping duplicates? Just a fancy dance move, doesn’t change the big picture.
- **Space Complexity**: O(n) for recursion stack + O(2^n * n) for output  
  - Recursion stack goes as deep as `n`. The output `sol` stores all subsets, and with duplicates handled, we still get up to 2^n unique subsets, each potentially size `n`. So, yeah, it’s a memory hog, but what did you expect from a subset party?

## Code (For Reference)
```cpp
class Solution {
public:
    void generateSubset(int idx, vector<int>& nums, vector<int>& ans, vector<vector<int>>& sol) {
        if (idx >= nums.size()) {
            sol.push_back(ans);
            return;
        }
        // Include current element
        ans.push_back(nums[idx]);
        generateSubset(idx + 1, nums, ans, sol);
        // Exclude and skip duplicates
        ans.pop_back();
        while (idx + 1 < nums.size() && nums[idx] == nums[idx + 1]) {
            idx++;
        }
        generateSubset(idx + 1, nums, ans, sol);
    }
    
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> sol;
        vector<int> ans;
        sort(nums.begin(), nums.end()); // Sort to handle duplicates
        generateSubset(0, nums, ans, sol);
        return sol;
    }
};
['Backtracking', 'Recursion', 'C++']