✅ Subset II | 2 Approaches (Backtracking & Iterative) || C++ | JAVA | Python
THIS PROBLEM IS VERY SIMILAR TO THIS PROBLEM\nNOW COMING TO THE PROBLEM AT HAND\nOBSERVATION TO BE MADE:\n If there are no duplicates the answer is directly 2^N
**THIS PROBLEM IS VERY SIMILAR TO [THIS PROBLEM](https://leetcode.com/problems/subsets/)**\n**NOW COMING TO THE PROBLEM AT HAND**\n**OBSERVATION TO BE MADE:**\n* If there are no duplicates the answer is directly `2^N`\n\t* This is because you have two choices for each element, either putting it into the subset or not.\n\n# **APPORACH I: Iterative**\n**Algorithm:**\nSuppose we have {1,2,3,3,3}\nNow after each iteration our 2-d vector becomes like this-\n```\n1. null\n2. null | 1\n3. null | 1 | 2 ; 1,2\n4. null | 1 | 2 ; 1,2 | 3; 1,3; 2,3; 1,2,3\n5. null | 1 | 2 ; 1,2 | 3; 1,3; 2,3; 1,2,3 | 3,3; 1,3,3; 2,3,3; 1,2,3,3\n6. null | 1 | 2 ; 1,2 | 3; 1,3; 2,3; 1,2,3 | 3,3; 1,3,3; 2,3,3; 1,2,3,3 | 3,3,3; 1,3,3,3; 2,3,3,3; 1,2,3,3,3\n```\nIf the number is a duplicate one, we just need to add this number to the last created subsets in the previous step.\n\n`In C++`\n```\nvector<vector<int> > subsetsWithDup(vector<int> &S) {\n    sort(S.begin(), S.end());\n    vector<vector<int>> ret = {{}};\n    int size = 0, startIndex = 0;\n    for (int i = 0; i < S.size(); i++) {\n        startIndex = i >= 1 && S[i] == S[i - 1] ? size : 0;\n        size = ret.size();\n        for (int j = startIndex; j < size; j++) {\n            vector<int> temp = ret[j];\n            temp.push_back(S[i]);\n            ret.push_back(temp);\n        }\n    }\n    return ret;\n}\n```\n`In JAVA`\n```\nclass Solution {\n    public List<List<Integer>> subsetsWithDup(int[] nums) {\n        Arrays.sort(nums);\n        List<List<Integer>> result = new ArrayList<List<Integer>>();\n        result.add(new ArrayList<Integer>());\n        int begin = 0;\n        for(int i = 0; i < nums.length; i++){\n            if(i == 0 || nums[i] != nums[i - 1]) begin = 0;\n            int size = result.size();\n            for(int j = begin; j < size; j++){\n                List<Integer> cur = new ArrayList<Integer>(result.get(j));\n                cur.add(nums[i]);\n                result.add(cur);\n            }\n            begin = size;\n        }\n        return result;\n    }\n}\n```\n`In Python`\n```\n def subsetsWithDup(self, nums):\n        """\n        :type nums: List[int]\n        :rtype: List[List[int]]\n        """\n        res = [[ ]]\n        nums.sort()\n        size = 0\n        for i in range(len(nums)):\n            j = size if i > 0 and (nums[i] == nums[i-1]) else 0\n            size = len(res)\n            while j < size:\n                temp = copy.copy(res[j])\n                temp.append(nums[i])\n                res.append(temp)\n                j += 1    \n        return res\n```\n**TIME COMPLEXITY: O(N)**\n\n# **APPROACH II: Backtracking**\nThe characteristics of C++ reference is an outstanding tool for backtracking algorithm!\n**Algorithm:**\nLet us use [1,2,3,4] as an example to explain my solution:\n```\nsubsets([1,2,3,4]) = []\n                     // push(1)\n                     [1, subsets([2,3,4])] // if push N times in subsets([2,3,4]), the pop times is also N, so vec is also [1] after backtrack.\n                     // pop(), push(2)\n                     [2, subsets([3,4])]\n                     // pop(), push(3)\n                     [3, subsets([4])]\n                     // pop(), push(4)\n                     [4, subsets([])]\n                     // pop()\n```\n**SOLUTION:**\n`In C++`\n```\nclass Solution {\npublic:\n    vector<vector<int> > subsetsWithDup(vector<int> &nums) {\n\t\tsort(nums.begin(), nums.end());\n        vector<std::vector<int>> res;\n\t\tvector<int> vec;\n\t\tsubsetsWithDup(res, nums, vec, 0);\n\t\treturn res;\n    }\nprivate:\n\tvoid subsetsWithDup(vector<vector<int> > &res, vector<int> &nums, vector<int> &vec, int begin) {\n\t\tres.push_back(vec);\n\t\tfor (int i = begin; i != nums.size(); ++i)\n\t\t\tif (i == begin || nums[i] != nums[i - 1]) { \n\t\t\t\tvec.push_back(nums[i]);\n\t\t\t\tsubsetsWithDup(res, nums, vec, i + 1);\n\t\t\t\tvec.pop_back();\n\t\t\t}\n\t}\n};\n```\n**TIME COMPLEXITY: O(2^N)**\n
[]