Перебор разбиений

[K-Dot]

Привет.Есть задание,в котором сказано,что имеется группа людей и рост каждого из них.Необходимо разбить всех на 2 группы так,чтобы суммарный рост двух групп был наиболее близок.
Как начал решать эту задачу я:
количество всех разбиений,как я думаю,будет равным числу Стирлинга второго порядка,т.к. это разбиения без повторений.Далее необходимо перебрать все возможные разбиения на 2.Каким способом это можно реализовать?Находил в интернете возможность работы с битовой маской,однако,как мне кажется,это слишком сложно и проще будет другим методом.

[K-Dot]

Думаю,что делать динамический двумерный массив для записи суммы каждого разбиения и элементов подмножеств будет затратно по памяти.Возможно стоит сделать один статический массив из 2-3 строк,где в 1 и 2 будут номера учеников входящих в 1 и 2 подмножества соответственно,а в 3 (хотя необязательно,можно рассчитать потом,при разборе предыдущих строк массива) разность сумм и/или рост каждого из 2х подмножеств.Если подскажите куда смотреть,чтобы понять,как перебирать все возможные разбиения,то буду очень благодарен.И правильно ли я понял,что нужно использовать числа Стирлинга 2го рода?Заранее спасибо!

[BDA]

Да, мне тоже кажется, что число Стирлинга 2го рода подходит для определения количества разбиений. Только это никак не помогает, на мой взгляд, искать сами разбиения. Битовая маска подходит отлично. Пусть группа людей состоит из N человек. Тогда возьмем маску длины N - 1 и переберем значения маски от 0...01 до 1...1. i-й бит маски интерпретируем как номер группы i-ого человека. При этом считаем, что N-й человек всегда в нулевой группе, а счет начинаем не с нуля, чтобы в первой группе тоже всегда был хотя бы один человек.
Например:
N = 4
0001
0010
0011
0100
0101
0110
0111
Серым цветом отмечен N-й человек.
Если N достаточно мало (например, до 32), то можно использовать одну переменную типа int для хранения и перебора масок.

[K-Dot]

Спасибо за ответ.

Сообщение от BDA

Например:
N = 4
0001
0010
0011
0100
0101
0110
0111

Т.е. при N=4 мы берем только 3 бита,серые,как я понял,это просто для того,чтобы показать и не относятся к битам?Если Вам не сложно,не могли бы вы расписать поподробнее (например при N=4).

[BDA]

Сначала я выписал все битовые маски при N=4 (получил 16 штук) и посмотрел на них. Во-первых, там было две маски 0000 и 1111, по которым получалась одна из групп пустая. Во-вторых, если рассмотреть произвольные две маски, например, 0110 и 1001 (одна, инверсия другой), то получится, что они задают одно и то же разбиение, ведь не важно, какая из групп первая, а какая вторая. Вот и получилось, что один бит закрепляется нулевым (считаем, что какой-то человек является главным в группе, то есть все люди делятся на тех, кто с ним, и кто не с ним). Тогда остается перебрать только значения для 3 битов, причем, дополнительно ограничить значения, чтобы вторая группа не получилась пустой. Вот и получается, что нужно перебрать все значения от 001 до 111. Если N<=33, тогда int хватит для хранения как раз 32битной маски (считаться будет долго). Вам остается только сделать цикл от 1 до ((1 << N) - 1) и на каждом шаге цикла считать сумму. Что именно вам тут непонятно? (т.е. я не очень понимаю, что расписать)