Пусть биты одного числа станут множеством

Иногда с целым множеством (набором элементов) нужно обращаться как с одним значением: перебирать такие значения в цикле и использовать их как индекс таблицы. Следующий шаг, битмаск-DP, делает именно это. Он упаковывает ответ на вопрос «какие элементы выбраны» в одно целое число и использует это число как индекс таблицы. С первой же строки он опирается на три приёма работы с битами, а общие уроки про биты будут только на шаге 132. Поэтому здесь эти три приёма показаны в самом простом виде: одно целое число вместо множества, пока без всякого DP.

Дан список из n элементов, и нужны все его подмножества. Подмножество задаётся тем, какие элементы внутри, а какие снаружи. Для ["a", "b"] их четыре: [], ["a"], ["b"], ["a", "b"].

Подмножеств ровно 2n: для каждого элемента отдельно решаешь, внутри он или снаружи, и эти решения не зависят друг от друга. Обойти все 2n вариантов проще всего так. Считай обычное целое число от 0 до 2n - 1, а биты каждого числа читай как ответы на вопросы «элемент i внутри?».