Вход в систему [2026/27, 10-профиль, Перебор подмножеств]
Общий подход к решению задач
Пусть дано множество из \(n\) элементов. Будем рассматривать различные способы выбрать несколько элементов из данных (без учёта порядка), то есть все возможные подмножества данного множества. Тогда каждое подмножество удобно кодировать строкой из \(n\) символов, равных 0 или 1, где \(i\)-й символ будет обозначать, входит ли \(i\)-й элемент в выбранное подмножество. Указанные строки также можно интерпретировать, как двоичные числа от 0 до \(2^n-1\), и перебрать все подмножества можно при помощи цикла:
for (int mask = 0; mask < 1 << n; ++mask) for mask in range(2 ** n):
а для определения, входит ли \(i\)-й элемент в данное подмножество удобно использовать битовые операции.