Сложность: medium
Дан массив целых чисел nums, содержащий уникальные элементы. Верните все возможные подмножества (степенной набор).
Множество решений не должно содержать дублирующихся подмножеств. Результат может быть возвращен в любом порядке.
Пример:
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
👨💻 Алгоритм:
1️⃣Определяем функцию обратного отслеживания под названием backtrack(first, curr), которая принимает индекс первого элемента, который нужно добавить, и текущую комбинацию в качестве аргументов.
2️⃣Если текущая комбинация завершена, мы добавляем её в итоговый вывод.
3️⃣В противном случае перебираем индексы i от first до длины всей последовательности n, добавляем элемент nums[i] в текущую комбинацию curr, продолжаем добавлять больше чисел в комбинацию: backtrack(i + 1, curr) и возвращаемся, удаляя nums[i] из curr.
😎 Решение:
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
def backtrack(first=0, curr=[]):
if len(curr) == k:
output.append(curr[:])
return
for i in range(first, n):
curr.append(nums[i])
backtrack(i + 1, curr)
curr.pop()
output = []
n = len(nums)
for k in range(n + 1):
backtrack()
return output
Ставь 👍 и забирай 📚 Базу знаний