✅Simple Backtrack Solution | Java | C++ | Python
IntuitionApproachComplexity
Time complexity: Worst case: O(2ⁿ * n)

Space complexity: O(2ⁿ * n)
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity: Worst case: O(2ⁿ * n)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(2ⁿ * n)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```java []
class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> ds = new ArrayList<>();
        int i=0;
        rec(i,nums,ds,ans);
        return ans;       
    }
    static void rec(int i,int[] nums,List<Integer> ds,List<List<Integer>> ans){
        if(i==nums.length){
            if(!ans.contains(ds))
            ans.add(new ArrayList<>(ds));
            return;
        }
        rec(i+1,nums,ds,ans);
        ds.add(nums[i]);
        rec(i+1,nums,ds,ans);
        ds.remove(ds.size()-1);
    }
}
```
```C++ []
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end()); // Sort to handle duplicates
        vector<vector<int>> ans;
        vector<int> ds;
        rec(0, nums, ds, ans);
        return ans;
    }

private:
    void rec(int i, vector<int>& nums, vector<int>& ds, vector<vector<int>>& ans) {
        if (i == nums.size()) {
            if (find(ans.begin(), ans.end(), ds) == ans.end()) 
                ans.push_back(ds);
            return;
        }

        rec(i + 1, nums, ds, ans);
        ds.push_back(nums[i]);
        rec(i + 1, nums, ds, ans);
        ds.pop_back();
    }
};
```
```python []
class Solution:
    def subsetsWithDup(self, nums):
        nums.sort()  # Sort to handle duplicates
        ans = []
        ds = []
        self.rec(0, nums, ds, ans)
        return ans

    def rec(self, i, nums, ds, ans):
        if i == len(nums):
            if ds not in ans:
                ans.append(ds[:])  # Add a copy of ds
            return
        
        self.rec(i + 1, nums, ds, ans)
        ds.append(nums[i])
        self.rec(i + 1, nums, ds, ans)
        ds.pop()
```


['Array', 'Backtracking', 'Python', 'Java', 'Python3']