Сложность: medium
Дан массив целых чисел nums, который может содержать повторяющиеся элементы. Верните все возможные подмножества (степенной набор).
Результирующий набор не должен содержать дублирующихся подмножеств. Возвращаемый результат может быть в любом порядке.
Пример:
Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
👨💻 Алгоритм:
1️⃣Отсортируйте массив nums. Сортировка необходима для того, чтобы все сгенерированные подмножества также были отсортированы. Это помогает идентифицировать дубликаты.
2️⃣Инициализируйте maxNumberOfSubsets максимальным количеством подмножеств, которые можно сгенерировать, т.е., 2 в степени n. Инициализируйте множество, seen, типа string, для хранения всех сгенерированных подмножеств. Добавление всех отсортированных подмножеств в множество дает нам возможность отловить любые дублирующие подмножества.
3️⃣Итерируйте от 0 до maxNumberOfSubsets - 1. Установленные биты в двоичном представлении subsetIndex указывают на позицию элементов в массиве nums, которые присутствуют в текущем подмножестве. Инициализируйте строку hashcode, которая будет хранить список чисел в текущемSubset в виде строки, разделенной запятыми. hashcode необходим для уникальной идентификации каждого подмножества с помощью множества. Выполните внутренний цикл for от j = 0 до n - 1, чтобы проверить позицию установленных битов в subsetIndex. Если на позиции j установлен бит, добавьте nums[j] в текущее подмножество currentSubset и добавьте nums[j] в строку hashcode. Добавьте текущее подмножество currentSubset в seen и в список подмножеств, если сгенерированный hashcode еще не в seen. Верните подмножества.
😎 Решение:
class Solution:
def subsetsWithDup(self, nums):
n = len(nums)
nums.sort()
maxNumberOfSubsets = 2**n
seen = set()
subsets = []
for subsetIndex in range(maxNumberOfSubsets):
currentSubset = []
hashcode = ""
for j in range(n):
mask = 2**j
isSet = mask & subsetIndex
if isSet != 0:
currentSubset.append(nums[j])
hashcode += str(nums[j]) + ","
if hashcode not in seen:
subsets.append(currentSubset)
seen.add(hashcode)
return subsets
Ставь 👍 и забирай 📚 Базу знаний