Recursion and Backtracking || Well Explained || 
IntuitionWhen generating all subsets for an array that contains duplicates, the key challenge is to avoid producing duplicate subsets. Sorting the array brings
# Intuition
When generating all subsets for an array that contains duplicates, the key challenge is to avoid producing duplicate subsets. Sorting the array brings duplicate elements together, which makes it easier to skip over them during recursion. In the backtracking process, for every element you face a binary decision: either include it in the current subset or exclude it. However, when excluding, you must skip all consecutive duplicate elements to ensure each subset is unique.

# Approach
1. Sort the Input Array:
Begin by sorting the array. This groups duplicate values together, making it easier to skip over them later.

2. Use Backtracking (Depth-First Search):
Define a recursive helper function that takes the current index, the temporary subset (curr), and the final answer container (ans).

3. Include the Current Element:

* Add the element at the current index to the curr subset.
* Recursively call the helper for the next index.
* After the recursive call, remove the element (backtrack) to restore the state.
4. Exclude the Current Element (Skip Duplicates):

* Instead of simply moving to the next index, skip all duplicate elements of the current number.
* This is done by advancing the index until you find a new value, then recursively calling the helper function starting from that new index.
5. Base Case:
When the current index reaches the size of the array, add the current subset to the answer list (ans).

This method guarantees that each decision to exclude a number is made only once for a group of duplicate numbers, which avoids duplicate subsets.

# Complexity
- Time complexity:
O(2^n)

- Space complexity:
O(2^n)

# Code
```java []
class Solution {
    public void generateSubsets(int index,List<List<Integer>> ans,int[] nums,List<Integer> list){
        if(index == nums.length){
            if(!ans.contains(list)){
                ans.add(new ArrayList<>(list));
            }
            return;
        }
        list.add(nums[index]);
        generateSubsets(index+1,ans,nums,list);
        list.remove(list.size()-1);
        generateSubsets(index+1,ans,nums,list);
    }
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> ans=new ArrayList<>();
        Arrays.sort(nums);
        generateSubsets(0,ans,nums,new ArrayList<>());
        return ans;
    }
}
```
```c++ []
class Solution {
public:
    void generateSubsets(int index, vector<vector<int>>& ans, vector<int>& nums, vector<int>& list) {
        if (index == nums.size()) {
            if (find(ans.begin(), ans.end(), list) == ans.end()) {
                ans.push_back(list);
            }
            return;
        }

        // Include the current element
        list.push_back(nums[index]);
        generateSubsets(index + 1, ans, nums, list);

        // Exclude the current element
        list.pop_back();
        generateSubsets(index + 1, ans, nums, list);
    }

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());  // Sort to handle duplicates properly
        vector<int> list;
        generateSubsets(0, ans, nums, list);
        return ans;
    }
};
```
```python []
class Solution:
    def generateSubsets(self, index, ans, nums, subset):
        if index == len(nums):
            if subset not in ans:  # Avoid duplicates
                ans.append(list(subset))
            return

        # Include the current element
        subset.append(nums[index])
        self.generateSubsets(index + 1, ans, nums, subset)

        # Exclude the current element
        subset.pop()
        self.generateSubsets(index + 1, ans, nums, subset)

    def subsetsWithDup(self, nums):
        ans = []
        nums.sort()  # Sort to handle duplicates
        self.generateSubsets(0, ans, nums, [])
        return ans
```
[![Upvote.png](https://assets.leetcode.com/users/images/1bb8c752-9349-4c7b-82cf-5df355c39e2b_1741071452.6723855.png)]()

['Array', 'Backtracking', 'C++', 'Java', 'Python3']