Subsets

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

Дан список разных чисел. Нужно вернуть все его подмножества: все наборы, которые можно выбрать, от пустого до всех чисел сразу, каждый набор один раз, в любом порядке. Наш пример: у [2, 5, 8] 2³ = 8 подмножеств, от [ ] и [2] до [2, 5, 8].

78 SubsetsРазбор · 1×

Пример: все подмножества [2, 5, 8]. Смотрите, как корень переходит к 5: дальше к ней может добавиться только 8, поэтому [5, 2] — то же, что [2, 5], — не появится.

[ ]22,52,5,82,855,88nums021528путь—результаты—
ещё не былипо пути сюдаэтот шагсохранённое подмножествонедоступно (до start) или только что убрано

Ищем все подмножества [2, 5, 8]

01/38
сначала · назад · пуск · шаг
Скорость
1function subsets(nums):
2 path = []
3 results = []
4 grow(0)
5 return results
6
7function grow(start):
8 add copy of path to results // each call is one
9 for i from start to len(nums) - 1:
10 path.add(nums[i])
11 grow(i + 1) // only numbers after nums[i]
12 path.removeLast()
состояние
start
–
i
–
path
–
results
–
нажмите шаг, чтобы вернуться

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

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

  1. Каждый вызов — это одно подмножество, путь, который к нему привёл, поэтому сохранение в начале вызова сохраняет все подмножества; в дереве ровно 2ⁿ вызовов.
  2. Вызов добавляет только числа после последнего взятого (start = i + 1). Тогда каждое подмножество собирается в одном порядке, по возрастанию индексов, и ни одно не сохраняется дважды.
  3. Число убирается, когда вызов вернулся, и путь становится прежним, поэтому следующее число цикла начинает с того же подмножества.

Сложность

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

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

Решить на LeetCode ↗

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