Python: Sort + BFS approach (without additional space)
Hello,\n\nThis solution is similar to the subset I problem solution. The explaination is below.\n\n\npython\n\ndef subsetsWithDup(self, nums: List[int]) -> List
Hello,\n\nThis solution is similar to the subset I problem solution. The explaination is below.\n\n\n```python\n\ndef subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n        \n\t\t# 1. Sort nums:\n        nums.sort()\n        \n\t\t# 2. Find all subsets:\n        combinations = [[]]\n        combinations_len = 1\n        for i in range(len(nums)):\n            \n\t\t\t# If duplicate, start from the new items appended by the previous val\n            start = combinations_len if i and nums[i] == nums[i - 1] else 0\n\t\t\t\n            combinations_len = len(combinations)            \n            for c in range(start, combinations_len):\n                combinations.append(combinations[c] + [nums[i]])\n                \n        return combinations\n\n```\n\n1- Intuition:\n- Subset problem (without duplicates):\n\t- Let\'s have the following input: [1,2,3] and let\'s `combinations` be our output\n\t- We\'ll start with `combinations = [[]]`\n\t- For each value `n` in `nums`, merge it with every existing `combination` and append it to the output list\n\t- For `n: 1`:  append( `[] + [1]`)  into `combinations = [[], [1]]`\n\t- For `n: 2`:  append( `[] + [2]`, `[1] + [2]`)  into `combinations = [[], [1], [2], [1,2]]`\n\t- For `n: 3`:  append( `[] + [3]`, `[1] + [3]`, `[2] + [3]`, `[1,2] + [3]` )  into `combinations = [[], [1], [2], [1,2], [1,2,3]]`\n\n- Subset II problem (with duplicates):\n\t- It\'s the same solution as the solution above. We just need to:\n\t\t- (1). Identify duplicates => Sort `nums`\n\t\t- (2). We need to avoid looping on all combinations when dealing with a duplicate. \n\t\t- We need to start from a specific position of the list `combinations`\n\t- Let\'s have the following input: [1,2,2,3,3] and suppose that it\'s already sorted\n\t- For the `1st. n: 2`:  `combinations = [[], [1], [2], [1,2]]`\n\t- For the `2nd. n: 2`:  \n\t\t- We need to avoid the existing combinations `[] + [2]`, `[1] + [2]` \n\t\t- We need to consider only `[2] + [2]` and `[1,2] + [2]`\n\t\t- In other words, we need to start from the combinations appended by previous `n: 2` \n\t\t- `combinations = [[], [1], [2], [1,2], [2, 2], [1,2,2]]`\n\t- For the `1st. n: 3`:  `combinations = [[], [1], [2], [1,2], [2, 2], [1,2,2], [3], [1,3], [2,3], [1,2,3], [2,2,3],[1,2,2,3]]`\n\t- For the `2nd. n:3`\n\t\t- We need to start from the combinations appended by previous `n: 3`: position: 6\n\t\t- We\'ll then append: `[3] + [3], [1,3] + [3] , ...,  [1,2,2,3] + [3]`\n\n2- Complexity Analysis:\n- Let\'s `n` be the number of values in `nums`\n- Time Complexity: `O(n * 2^n)`\n\t\t- The output `combinations` doubles for every value in `nums`: `O(2^n)` combinations (including duplicates)\n\t\t- Every combination is created from merging a previous combination with a value: T(merge): `O(n)`\n- Space Complexity: `O(n * 2^n)` (same as above)\n
['Breadth-First Search', 'Python', 'Python3']