Subsets II

Средняя№90подмножества

Дан список чисел, и некоторые могут повторяться. Нужно вернуть все разные подмножества: все наборы, которые можно выбрать, от пустого до всех чисел, и ни один набор дважды, даже если равные числа дают его другим способом. Наш пример: у [3, 1, 3] 6 таких подмножеств: [ ], [1], [1, 3], [1, 3, 3], [3] и [3, 3].

90 Subsets IIРазбор · 1×

Пример: все разные подмножества [3, 1, 3]. Смотрите на вторую 3: в корне её пропускаем, ведь [3] уже есть, а сразу после первой 3 её берём, и получается [3, 3].

[ ]11,31,3,333,3nums031123путь—результаты—
ещё не былипо пути сюдаэтот шагсохранённое подмножествопропущено: повторяет ветку перед нимдо start: недоступно

Ищем все разные подмножества [3, 1, 3]: 3 встречается дважды

01/32
сначала · назад · пуск · шаг
Скорость
1function subsetsWithDup(nums):
2 sort(nums) // equal numbers side by side
3 path = []
4 results = []
5 grow(0)
6 return results
7
8function grow(start):
9 add copy of path to results
10 for i from start to len(nums) - 1:
11 if i > start and nums[i] == nums[i-1]: continue
12 path.add(nums[i])
13 grow(i + 1)
14 path.removeLast()
состояние
nums
[3, 1, 3]
start
–
i
–
path
–
results
–
нажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. После сортировки равные числа стоят рядом, поэтому повтор легко заметить: он равен числу прямо перед ним.
  2. В одном вызове ветка, которая начинается с повтора, собрала бы те же подмножества, что ветка первой копии, поэтому i > start при nums[i] == nums[i - 1] пропускаем.
  3. При i == start число встаёт за только что взятым, а не начинает соседнюю ветку, поэтому вторая 3 после первой даёт новое: так [3, 3] и [1, 3, 3] появляются ровно один раз.

Сложность

Время O(n × 2ⁿ): сортировка — O(n log n), потом не больше 2ⁿ вызовов, и каждый копирует путь длиной до n. Память O(n) помимо ответа: путь и стек вызовов не глубже n.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.