Генерация всех подмножеств
Выбирайте каждый элемент или пропускайте его
«Генерация всех подмножеств» — бесплатный урок Competitive Programming Academy на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Competitive Programming Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Competitive Programming Academy содержит 4 уроков всего.
Зачем генерировать подмножества
Во многих задачах соревнований требуется перебрать каждое подмножество небольшого множества. С помощью рекурсии можно перечислить их чисто и надёжно. 🧩
Выбирайте или пропускайте каждый элемент
Основная идея такова: для каждого элемента нужно сделать один двоичный выбор — включить его или оставить за пределами подмножества. Каждый полный набор выборов задаёт одно подмножество.
Сколько существует подмножеств
Множество из n элементов имеет ровно 2 в степени n подмножеств, потому что каждый элемент удваивает их количество. Поэтому значение n должно быть небольшим — примерно 20 или меньше.
Рекурсивный план
Перемещайте индекс по массиву. На каждом индексе создавайте две ветви: в одной берите элемент, в другой пропускайте его.
Базовый случай
Когда индекс проходит последний элемент, текущий путь становится одним полным подмножеством. Это и есть ваш базовый случай, в котором его нужно сохранить.
Рекурсия для подмножеств в коде
Этот рекурсивный проход сохраняет подмножество в конце, а затем для каждого индекса исследует варианты пропуска и выбора элемента.
def gen(i, cur):
if i == len(a):
out.append(cur[:])
return
gen(i + 1, cur)
gen(i + 1, cur + [a[i]])Выполняйте возврат, отменяя выбор
Добавив элемент, удалите его после рекурсивного вызова, чтобы следующая ветвь начиналась с чистого состояния. Этот шаг отмены — основа поиска с возвратом.
cur.append(a[i])
gen(i + 1, cur)
cur.pop()Альтернатива с битовой маской
Можно также сопоставить каждому целому числу от 0 до 2 в степени n минус 1 одно подмножество, где каждый бит отмечает включённый элемент.
for mask in range(1 << n):
sub = [a[i] for i in range(n) if mask >> i & 1]Делайте копию перед сохранением
Всегда сохраняйте копию текущего списка, а не сам список. Иначе последующие изменения перезапишут каждое сохранённое подмножество. ⚠️
Генерация сочетаний
Чтобы получить подмножества фиксированного размера k, прекращайте ветвь, как только количество выбранных элементов достигнет k. Так подмножества превращаются в сочетания.
Где встречаются подмножества
Перебор подмножеств решает небольшие задачи о рюкзаке, выборе команды и проверке допустимости, когда нужно проверить каждый возможный выбор.
Быстрая проверка
Сколько подмножеств содержит множество из n элементов?
Повторение: ветвитесь на каждом элементе
Вы научились перечислять все подмножества, выбирая или пропуская каждый элемент и отменяя выбор после каждой ветви. Значение n должно быть небольшим, поскольку количество подмножеств равно 2 в степени n. 🎯
Часто задаваемые вопросы
Урок «Генерация всех подмножеств» бесплатный?
Да — полный текст урока «Генерация всех подмножеств» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Competitive Programming Academy, подпишись на CoddyKit PRO. Курс Competitive Programming Academy содержит 4 уроков всего.
Чему я научусь в уроке «Генерация всех подмножеств»?
Выбирайте каждый элемент или пропускайте его Ты практикуешь Competitive Programming Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Competitive Programming Academy?
Предыдущий опыт не требуется. Competitive Programming Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.
Сколько времени занимает урок «Генерация всех подмножеств»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Competitive Programming Academy?
Да. Каждый урок Competitive Programming Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Рекурсивное мышление: база и рекурсия
- Генерация всех подмножеств
- Перестановки и идея задачи о N ферзях
- Сокращение поиска ради соблюдения лимита времени