Как разбить множество на всевозможные два подмножества с равной суммой элементов?
Необходимо построить алгоритм, который по заданному множеству определяет, можно ли его разбить на два подмножества с равной суммой элементов. Если да, то выписать все такие множества с точностью до перестановок
Например, множество [1,2,3,4,5,6,7] разбивается на [7, 6, 1] [5, 4, 3, 2] , [7, 5, 2]
[6,4,3,1] , [7, 4, 3] [6,5,2,1] и [7, 4, 2, 1] [6,5,3] (т.е. [7, 6, 1] и [7, 1, 6] одинаковы)
Есть понимание, что сумма всех элементов должна делиться на два. А дальше возникают трудности.
Ну, самое тупое - отсортировать множество по возрастанию (1 - 7) и перебирать его перестановки по принципу счетчика.
На каждой итерации проверяем, получается ли сумма первых n элементов равной половине суммы всего множества. Такой набор (со всеми перестановками второй части) будет решением. Если не сложилось - пропускаем все перестановки до изменения n-ого (или (n-1)-ого) элемента, потом продолжаем.
P.S. Собственно, раз вам нужно с точностью до перестановки - вам и счетчик нужно увеличивать с условием, что все элементы от первого до n-ного отсортированы по возрастанию.
Полный перебор. Вам надо найти множества, имеющие сумму в половину от суммы всех чисел.
Можно итеративно - перебирайте число от 0 до 2^|количество чисел|. Биты в этом числе будут обозначать, берется ли конкретный элемент множества в сумму. Дальше считайте сумму текущего подмножества пользуясь бытовыми операциями, чтобы проверить стоит ли заданный бит в 0 или 1. Если набрали половину общей суммы - выводите те индексы, где биты 1 как одно множество, а оставшиеся - как второе. Чтобы каждое разбиение не выводить 2 раза, требуйте, чтобы старший бит был 0 (перебирайте до 2^|количество чисел-1|)
Можно рекурсивно. Рекурсивная функция принимает текущий набор чисел и номер следующего числа кандидата. Функция или берет или не берет текущего кандидата и запускается рекурсивно передавая следющий номер как кандидата. Если все числа рассмотрены - проверяйте сумму и выводите разбиение. Можно соптимизировать - если уже набрали сумму больше половины, дальше перебирать смысла нет. Опять же, первое число можно потребовать всегда брать или всегда не брать, чтобы не выводить одно и то же разбиение 2 раза.
marshmallow, Alexandroppolus,
Динамическое программирование позволило бы быстрее подсчитать сколько таких множеств есть или проверить, а есть ли они вообще. Раз в задаче надо их сами вывести, то задача решается только полным перебором. С помощью ДП его можно ускорить, но не во всех случаях, поэтому заморачиваться смысла нет.
Средний
