степенное множество

EN: power set

Множество всех подмножеств данного множества, включая пустое множество и само множество. Множество из n элементов имеет 2ⁿ подмножеств. Генерация степенного множества через backtracking — для каждого элемента выбор «включить или нет» — занимает O(n · 2ⁿ) времени, так как 2ⁿ подмножеств, и копирование каждого стоит O(n).