Выбор ответа Middle Биты обновлено
Подмножества через маску
Вопрос
Как перебрать все подмножества массива из n элементов (n ≤ 20) без рекурсии?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Цикл по mask от 0 до (1 << n) - 1, бит i задаёт элемент. Каждое число от 0 до 2ⁿ - 1 своими битами задаёт подмножество.
Варианты ответа
- Цикл по
maskот 0 до n, элемент i входит приmask === i - Сортировка и два указателя, сдвигаемые навстречу друг другу
- Цикл по
maskот 1 доn ** 2, биты маски задают элементы - Цикл по
maskот 0 до(1 << n) - 1, бит i задаёт элементправильный ответ
Разбор
Каждое число от 0 до 2ⁿ - 1 своими битами задаёт подмножество. O(n · 2ⁿ). Работает пока 1 << n помещается в 32 бита, то есть n до 30; на практике перебор и так ограничен n около 20.
- n масок недостаточно, их нужно 2ⁿ.
- Указатели не перебирают подмножества.
- n² масок это не все подмножества.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.