✅☑️ Best C++ 2 Solution Ever || Easy Solution || Backtracking || One Stop Solution.
Intuition\n Describe your first thoughts on how to solve this problem. \nWe can solve this problem using Array + Backtracking.\n\n# Approach\n Describe your app
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe can solve this problem using Array + Backtracking.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe can easily understand the all the approaches by seeing the code which is easy to understand with comments.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nTime complexity is given in code comment.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nSpace complexity is given in code comment.\n\n# Code\n```\n/*\n\n    Time complexity : O(2^N*2^N), For every index, we make 2 recursion calls and there are N elements and for\n    every subset we are checking duplicates in output and in worst case it can contain 2^N-1 subset. so total time\n    complexity is O(2^N*2^N).\n\n    Space complexity : O(2^N*N), In worst case there can be 2^N-1 subsets and for every subset, we need O(N) \n    space on average so total space complexity is O(2^N*N).\n\n    Solved using Array + Backtracking.\n\n*/\n\n\n/***************************************** Approach 1 *****************************************/\n\nclass Solution {\nprivate: \n    void subsetsWithDup(vector<int>& nums, vector<vector<int>> &output, vector<int> temp, int index) {\n        if(nums.size() == index){\n            bool isPresent = find(output.begin(), output.end(), temp) != output.end();\n            if(!isPresent){\n                output.push_back(temp);\n            }\n            return;\n        }\n        subsetsWithDup(nums, output, temp, index+1);\n        temp.push_back(nums[index]);\n        subsetsWithDup(nums, output, temp, index+1);\n    }\npublic:\n    vector<vector<int>> subsetsWithDup(vector<int>& nums) {\n        sort(nums.begin(), nums.end());\n        vector<int> temp;\n        vector<vector<int>> output;\n        subsetsWithDup(nums, output, temp, 0);\n        return output;\n    }\n};\n\n\n\n\n\n\n/*\n\n    Time complexity : O(2^N).\n\n    Space complexity : O(2^N*N), In worst case there can be 2^N-1 subsets and for every subset, we need O(N) \n    space on average so total space complexity is O(2^N*N).\n\n    Solved using Array + Backtracking.\n\n*/\n\n\n/***************************************** Approach 2 *****************************************/\n\nclass Solution {\npublic:\n    void solve(vector<int> &nums, vector<int> &ds, vector<vector<int>> &ans, int ind){\n        ans.push_back(ds);\n        for(int i=ind;i<nums.size();i++)\n        {\n            if(i>ind && nums[i] == nums[i-1]){\n                continue;\n            }\n            ds.push_back(nums[i]);\n            solve(nums,ds,ans,i+1);\n            ds.pop_back();\n        }\n    }\n    vector<vector<int>> subsetsWithDup(vector<int>& nums){\n        vector<vector<int>> ans;\n        sort(nums.begin(),nums.end());\n        vector<int> ds;\n        solve(nums,ds,ans,0);\n        return ans;\n    }\n};\n\n\n```\n\n***IF YOU LIKE THE SOLUTION THEN PLEASE UPVOTE MY SOLUTION BECAUSE IT GIVES ME MOTIVATION TO REGULARLY POST THE SOLUTION.***\n\n![WhatsApp Image 2023-02-10 at 19.01.02.jpeg](https://assets.leetcode.com/users/images/0a95fea4-64f4-4502-82aa-41db6d77c05c_1676054939.8270252.jpeg)
['Array', 'Backtracking', 'C++']