[C++/Python] Bitmasking, Backtracking, Iterative Solutions - with Picture - Clean & Concise
\u2714\uFE0F Solution 1: Bitmasking (with Hashing)\n- In a nums array of length n, there are total 2^n possible subsets.\n- The idea is that we use bitmasks of 
**\u2714\uFE0F Solution 1: Bitmasking (with Hashing)**\n- In a `nums` array of length `n`, there are total `2^n` possible subsets.\n- The idea is that we use bitmasks of `n` bits to present the state of subsets, `mask` in `[0, 1, ... 2^n-1]`. If the `i`th bit in the `mask` is `1` means `nums[i]` exists in the subset presented by `mask`.\n- Since the `nums` array may contain duplicate numbers, so in the `2^n` subsets, it may contain duplicate subsets. \n\t- We need to sort `nums` array to ensure all the generated subsets will also be sorted. This helps to identify duplicates. For example: subsets {3, 1, 3}, {1, 3, 3}, {3, 3, 1} will become {1, 3, 3}.\n\t- We need to hash the subset and add into a HashTable, let\'s name `seen`, to check for duplicates.\n\n<iframe src="https://leetcode.com/playground/FqjVD8Dq/shared" frameBorder="0" width="100%" height="500"></iframe>\n\n**Complexity**\n- Time: `O(2^N * N)`, where `N <= 10` is length of `nums` array.\n- Space: `O(2^N)`\n---\n**\u2714\uFE0F Solution 2: Backtracking version 1 (without Hashing)**\n- We traverse the tree in PreOrder, starting with `index = 0`, for each `index`, we iterate elements from `nums[index]...nums[n-1]`.\n- Since the `nums` array may contain duplicate numbers, so in the `2^n` subsets, it may contain duplicate subsets. \n\t- We need to sort `nums` array to ensure all the generated subsets will also be sorted. This helps to identify duplicates. For example: subsets {3, 1, 3}, {1, 3, 3}, {3, 3, 1} will become {1, 3, 3}.\n\t- If numbers are duplicates, we keep the first time, otherwise we skips. We can see it clearly through following picture.\n\n![image](https://assets.leetcode.com/users/images/f2fc14d2-fcf7-4d31-8844-0489a9b83281_1628047166.1461427.png)\n\n```python\nclass Solution:\n    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n        def backtrack(index, curSubset):\n            ans.append(curSubset[::])\n\n            for i in range(index, len(nums)):\n                if i > index and nums[i] == nums[i - 1]: continue  # Skip duplicates\n                curSubset.append(nums[i])\n                backtrack(i + 1, curSubset)\n                curSubset.pop()\n\n        nums.sort()\n        ans = []\n        backtrack(0, [])\n        return ans\n```\n\n**Complexity**\n- Time: `O(2^N * N)`, where `N <= 10` is length of `nums` array.\n- Space: `O(2^N)`\n\n---\n\n**\u2714\uFE0F Solution 3: Backtracking version 2 (without Hasing)**\n- For each elements of `nums`, there are 2 options: **pick** or **don\'t pick** that number, so there is total **2^n** possible subsets.\n- Since the `nums` array may contain duplicate numbers, so in the `2^n` subsets, it may contain duplicate subsets. \n\t- We need to sort `nums` array to ensure all the generated subsets will also be sorted. This helps to identify duplicates. For example: subsets {3, 1, 3}, {1, 3, 3}, {3, 3, 1} will become {1, 3, 3}.\n\t-  In don\'t pick choice, we only call it if the last element in current subset different with  `nums[i]` otherwise duplicate occurs.\n```python\nclass Solution:\n    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n        def backtrack(i, curSubset):\n            if i == len(nums):\n                ans.append(curSubset[::])\n                return\n\n            curSubset.append(nums[i])\n            backtrack(i + 1, curSubset)  # Pick\n            curSubset.pop()\n\n            if not curSubset or curSubset[-1] != nums[i]:\n                backtrack(i + 1, curSubset)  # Don\'t pick\n\n        nums.sort()\n        ans = []\n        backtrack(0, [])\n        return ans\n```\n**Complexity**\n- Time: `O(2^N * N)`, where `N <= 10` is length of `nums` array.\n- Space: `O(2^N)`\n\n---\n\n**\u2714\uFE0F Solution 4: Iterative (with Hashing)**\n- The idea is that we start with an empty subset.\n- For each element `num` in `nums`, we iterate all all previous subsets, create new subsets by adding each previous subsets with `num`.\n- For example: `nums = [1, 2, 3]`\n\t- First at all, `ans = [[]]`\n\t- Step 1, with `nums[0] = 1`, `ans = [[], [1]]`\n\t- Step 2, with `nums[1] = 2`, `ans = [[], [1], [2], [1, 2]]`\n\t- Step 3, with `nums[2] = 3`, `ans = [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]`\n```python\nclass Solution:\n    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n        nums.sort()\n        ans = set()\n        ans.add(tuple())\n        \n        for num in nums:\n            newSubsets = set()\n            for subset in ans:  # Iterate previous subsets from ans\n                newSubsets.add(tuple(list(subset) + [num]))\n            ans.update(newSubsets)  # Add new subsets to ans\n\t\t\t\n        return ans\n```\n**Complexity**\n- Time: `O(2^N * N)`, where `N <= 10` is length of `nums` array.\n- Space: `O(2^N)`\n\nIf you think this **post is useful**, I\'m happy if you **give a vote**. Any **questions or discussions are welcome!** Thank a lot.
[]