Генерация всех подмножеств

Генерация всех подмножеств (Power Set)

Это классическая задача на комбинаторику. Для множества размером n существует ровно 2^n подмножеств.

1. Анализ проблемы

Подмножество (subset) — это любое подмножество исходного множества, включая пустое и само множество.

Количество подмножеств: 2^n

Для [1, 2, 3]: 2³ = 8 подмножеств
  Пустое: []
  Размер 1: [1], [2], [3]
  Размер 2: [1,2], [1,3], [2,3]
  Размер 3: [1,2,3]

Причина 2^n: Для каждого элемента мы решаем: включить или не включить.

2. Решение 1: Встроенная функция

from itertools import combinations

def subsets_builtin(nums: list[int]) -> list[list[int]]:
    """Использование itertools.combinations."""
    result = [[]]
    
    for i in range(1, len(nums) + 1):
        result.extend(combinations(nums, i))
    
    return [list(combo) for combo in result]

# Альтернатива через itertools.chain
from itertools import chain, combinations

def subsets_chain(nums: list[int]) -> list[list[int]]:
    """Более элегантно."""
    return [list(combo) for combo in chain.from_iterable(
        combinations(nums, r) for r in range(len(nums) + 1)
    )]

print(subsets_builtin([1, 2, 3]))

3. Решение 2: Рекурсия (Backtracking)

def subsets_recursive(nums: list[int]) -> list[list[int]]:
    """Генерация подмножеств через рекурсию."""
    result = []
    
    def backtrack(path, start):
        # Добавляем текущее подмножество
        result.append(path[:])
        
        # Рекурсивно добавляем элементы
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(path, i + 1)  # start = i + 1 для избежания дубликатов
            path.pop()
    
    backtrack([], 0)
    return result

print(subsets_recursive([1, 2, 3]))

Визуализация дерева рекурсии для [1, 2, 3]:

                    []
                    |
          ┌─────────┼─────────┐
          |         |         |
         [1]       [2]       [3]
         / \       / \       |
       [1,2] [1,3] [2,3]  (лист)
       /        |       \
    [1,2,3]  (лист)   (лист)

Обход (DFS):
1. [] ← добавляем
2. Добавляем 1 → [1]
3. [] добавляем [1]
4. Добавляем 2 → [1,2]
5. Добавляем [1,2]
6. Добавляем 3 → [1,2,3]
7. Добавляем [1,2,3]
...

4. Решение 3: Итеративный подход (Битовые маски)

def subsets_iterative(nums: list[int]) -> list[list[int]]:
    """Генерация подмножеств через битовые маски."""
    n = len(nums)
    result = []
    
    # Для каждого числа от 0 до 2^n - 1
    for i in range(2 ** n):
        subset = []
        
        # Проверяем каждый бит
        for j in range(n):
            if i & (1 << j):  # Если j-й бит установлен
                subset.append(nums[j])
        
        result.append(subset)
    
    return result

print(subsets_iterative([1, 2, 3]))

Как это работает?

Для [1, 2, 3] (n=3):

i=0: 000 → (пусто)
i=1: 001 → [1]       (бит 0 установлен)
i=2: 010 → [2]       (бит 1 установлен)
i=3: 011 → [1, 2]    (биты 0 и 1 установлены)
i=4: 100 → [3]       (бит 2 установлен)
i=5: 101 → [1, 3]    (биты 0 и 2 установлены)
i=6: 110 → [2, 3]    (биты 1 и 2 установлены)
i=7: 111 → [1, 2, 3] (все биты установлены)

5. Решение 4: Инкрементальный (Adding elements)

def subsets_incremental(nums: list[int]) -> list[list[int]]:
    """Добавляем элементы по одному."""
    result = [[]]
    
    for num in nums:
        # Для каждого нового элемента
        # удваиваем количество подмножеств
        result.extend([subset + [num] for subset in result])
    
    return result

print(subsets_incremental([1, 2, 3]))

Визуализация:

Шаг 0: result = [[]]

Шаг 1: Добавляем 1
  Берём все существующие подмножества: [[]]
  Добавляем 1 к каждому: [[1]]
  result = [[], [1]]

Шаг 2: Добавляем 2
  Берём все существующие подмножества: [[], [1]]
  Добавляем 2 к каждому: [[2], [1,2]]
  result = [[], [1], [2], [1,2]]

Шаг 3: Добавляем 3
  Берём все существующие подмножества: [[], [1], [2], [1,2]]
  Добавляем 3 к каждому: [[3], [1,3], [2,3], [1,2,3]]
  result = [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

6. Полная реализация с тестами

from typing import List
import unittest

class Solution:
    @staticmethod
    def subsets(nums: List[int]) -> List[List[int]]:
        """Оптимальное решение: инкрементальное добавление."""
        result = [[]]
        
        for num in nums:
            result.extend([subset + [num] for subset in result])
        
        return result


class TestSubsets(unittest.TestCase):
    
    def test_three_elements(self):
        """Пример из задачи."""
        nums = [1, 2, 3]
        result = Solution.subsets(nums)
        expected = [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]
        self.assertEqual(len(result), 8)
        for subset in expected:
            self.assertIn(subset, result)
    
    def test_single_element(self):
        """Один элемент."""
        nums = [1]
        result = Solution.subsets(nums)
        expected = [[], [1]]
        self.assertEqual(result, expected)
    
    def test_empty_list(self):
        """Пустой список."""
        nums = []
        result = Solution.subsets(nums)
        expected = [[]]
        self.assertEqual(result, expected)
    
    def test_two_elements(self):
        """Два элемента."""
        nums = [1, 2]
        result = Solution.subsets(nums)
        self.assertEqual(len(result), 4)
        for subset in [[], [1], [2], [1, 2]]:
            self.assertIn(subset, result)
    
    def test_four_elements(self):
        """Четыре элемента (16 подмножеств)."""
        nums = [1, 2, 3, 4]
        result = Solution.subsets(nums)
        self.assertEqual(len(result), 16)
        # Все подмножества уникальны
        unique = {tuple(sorted(subset)) for subset in result}
        self.assertEqual(len(unique), 16)

if __name__ == '__main__':
    unittest.main()

7. Особые случаи: подмножества размером k

def subsets_of_size_k(nums: List[int], k: int) -> List[List[int]]:
    """Генерирует только подмножества размером ровно k."""
    result = []
    
    def backtrack(path, start):
        if len(path) == k:
            result.append(path[:])
            return
        
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(path, i + 1)
            path.pop()
    
    backtrack([], 0)
    return result

print(subsets_of_size_k([1, 2, 3, 4], 2))
# [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]

8. Сравнение методов

9. Анализ сложности

Время:
- 2^n подмножеств
- Каждое подмножество имеет среднюю длину n/2
- Копирование каждого: O(n)
- Итого: O(2^n × n)

Память (результат):
- 2^n подмножеств
- Средняя длина: n/2
- Итого: O(2^n × n)

10. Оптимизация для больших n

def subsets_generator(nums: List[int]):
    """Ленивая генерация подмножеств."""
    def backtrack(path, start):
        yield path[:]
        
        for i in range(start, len(nums)):
            path.append(nums[i])
            yield from backtrack(path, i + 1)
            path.pop()
    
    yield from backtrack([], 0)

# Использование
for subset in subsets_generator([1, 2, 3]):
    print(subset)

11. Подмножества с дубликатами

def subsets_unique(nums: List[int]) -> List[List[int]]:
    """Подмножества с дубликатами в исходных данных."""
    nums.sort()
    result = [[]]
    
    start = 0
    for i in range(len(nums)):
        # Если это дубликат, пропускаем старые подмножества
        if i > 0 and nums[i] == nums[i-1]:
            start = len(result) - start
        
        size = len(result)
        for j in range(start, size):
            result.append(result[j] + [nums[i]])
        
        start = size
    
    return result

print(subsets_unique([1, 2, 2]))
# [[], [1], [2], [1,2], [2,2], [1,2,2]]

Вывод

Для генерации подмножеств:

1. Лучше всего: Инкрементальный метод (простой, быстрый)
2. На интервью: Рекурсия/Backtracking (понимание алгоритма)
3. Для production: itertools.combinations (надёжно)
4. Для уникальности: Сортировка + отслеживание дубликатов
5. Для памяти: Генераторы с yield

Сложность: O(2^n × n) — неизбежна, это размер результата.

Это фундаментальная задача на комбинаторику — хорошо её знайте!