Выбор ответа Junior Перебор с возвратом спрашивают часто обновлено
Сколько подмножеств
Вопрос
Сколько подмножеств у множества из n элементов и какая сложность их генерации?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: 2ⁿ, O(n · 2ⁿ) с копированием каждого. Каждый элемент либо входит, либо нет: 2ⁿ подмножеств.
Варианты ответа
- 2ⁿ, O(n · 2ⁿ) с копированием каждогоправильный ответ
- n², O(n²): пары элементов
- n!, O(n!): все перестановки
- 2n, O(n): взять или не взять
Разбор
Каждый элемент либо входит, либо нет: 2ⁿ подмножеств. Копирование каждого в ответ стоит до O(n), итого O(n · 2ⁿ).
- n² сильно меньше настоящего числа.
- n! это число перестановок.
- 2n не имеет отношения к задаче.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.
Предыдущий вопрос
Отсечение в сумме комбинаций
Следующий вопрос
Все правильные скобочные последовательности