✅☑Beats 100% users || [C++/Java/Python/JavaScript] || EXPLAINED🔥
PLEASE UPVOTE IF IT HELPED\n\n---\n\n\n---\n\n\n# Approaches\n(Also explained in the code)\n\n1. Sorting the Input:\n\n    - Initially, the nums vector is sorte
# PLEASE UPVOTE IF IT HELPED\n\n---\n![Screenshot 2024-01-04 012641.png](https://assets.leetcode.com/users/images/95de3c52-4515-437c-a6e3-0a77b42fe1d6_1704311828.1091535.png)\n\n---\n\n\n# Approaches\n(Also explained in the code)\n\n1. **Sorting the Input:**\n\n    - Initially, the `nums` vector is sorted in ascending order. This sorting helps in identifying duplicates and ensures that identical elements appear consecutively.\n1. **Recursive Backtracking (f function):**\n\n    - The `f` function generates subsets using a recursive backtracking approach.\n    - It maintains an index (`index`) that tracks the position of the current element being considered for inclusion in the subset.\n    - It starts by adding the current subset `t` into the `ans` vector of subsets.\n1. **Iteration through Elements:**\n\n    - The function iterates through the elements of `nums` starting from the `index` position.\n    - It checks for duplicates by ensuring that if `i` is not equal to `index` (not considering the same index) and the current element is the same as the previous one, it skips duplicates using `continue`.\n1. **Building Subsets:**\n\n    - For each valid element, it adds that element to the subset `t`, calls the `f` function recursively with the next index `i + 1`, and explores further elements to create subsets that include the current element.\n    - After the recursive call, it removes the last added element from the `t` subset (`t.pop_back()`) to backtrack and explore other possibilities.\n1. **Subset Generation:**\n\n    - As the recursion unwinds, it generates different combinations of subsets by adding and removing elements, eventually leading to the generation of all unique subsets without duplicates.\n1. **Return:**\n\n    - Finally, all subsets (including duplicates) are collected in the `ans` vector and returned as the result.\n\n\n\n# Complexity\n- Time complexity:\n   $$O(2^n*n)$$\n    \n\n- Space complexity:\n   $$O(2^n*k)$$\n    \n\n\n# Code\n```C++ []\nclass Solution {\nprivate:\n    void f(int index, vector<int>& nums, vector<int>& t, vector<vector<int>>& ans){\n        ans.push_back(t);\n\n        for(int i = index; i < nums.size(); i++){\n            if(i != index && nums[i] == nums[i-1]) continue;\n            t.push_back(nums[i]);\n            f(i + 1, nums, t, ans); \n            t.pop_back();\n        }\n    }\n\npublic:\n    vector<vector<int>> subsetsWithDup(vector<int>& nums) {\n        vector<vector<int>> ans;\n        vector<int> t;\n\n        sort(nums.begin(), nums.end());\n        f(0, nums, t, ans);\n        return ans;\n    }\n};\n\n\n\n\n\n```\n```Java []\n\n\nclass Solution {\n    private void f(int index, int[] nums, List<Integer> t, List<List<Integer>> ans) {\n        ans.add(new ArrayList<>(t));\n\n        for (int i = index; i < nums.length; i++) {\n            if (i != index && nums[i] == nums[i - 1]) continue;\n            t.add(nums[i]);\n            f(i + 1, nums, t, ans);\n            t.remove(t.size() - 1);\n        }\n    }\n\n    public List<List<Integer>> subsetsWithDup(int[] nums) {\n        List<List<Integer>> ans = new ArrayList<>();\n        List<Integer> t = new ArrayList<>();\n\n        Arrays.sort(nums);\n        f(0, nums, t, ans);\n        return ans;\n    }\n}\n\n\n\n```\n```python3 []\nclass Solution:\n    def subsetsWithDup(self, nums):\n        def f(index, t):\n            ans.append(list(t))\n            \n            for i in range(index, len(nums)):\n                if i != index and nums[i] == nums[i - 1]:\n                    continue\n                t.append(nums[i])\n                f(i + 1, t)\n                t.pop()\n\n        ans = []\n        nums.sort()\n        f(0, [])\n        return ans\n\n\n\n```\n```javascript []\nvar subsetsWithDup = function(nums) {\n    const ans = [];\n    nums.sort((a, b) => a - b);\n\n    function f(index, t) {\n        ans.push([...t]);\n\n        for (let i = index; i < nums.length; i++) {\n            if (i !== index && nums[i] === nums[i - 1]) continue;\n            t.push(nums[i]);\n            f(i + 1, t);\n            t.pop();\n        }\n    }\n\n    f(0, []);\n    return ans;\n};\n\n\n\n```\n---\n\n\n\n# PLEASE UPVOTE IF IT HELPED\n\n---\n---\n\n\n---
['Array', 'Backtracking', 'Bit Manipulation', 'Python', 'C++', 'Java', 'Python3', 'JavaScript']