Особый алгоритм перебора всех подмножеств мультимножества

[B@R5uk]

B@R5uk в сообщении #1287659 писал(а):

Я придумал простой и действенный способ пропуска недолётов. Вот наглядный пример.
1001010001 = 42 (45). Проверяем
xxx0010001 = ?? (45), используя для предварительно посчитанный массив кумулятивных сумм первых элементов исходного множества. Если недолёт, то переходим к
1000010001 = 32 (45). Если перелёт, то необходим полный перебор, поэтому переходим к
0010010001 = 36 (45). Если же попадание, то это можно сразу зафиксировать, а затем, как и в случае недолёта, перейти к
1000010001 = 32 (45).

Пытаюсь понять, как переложить это на случай перебора с учётом повторов. Допустим у нас есть числа
aaabcddef, и находимся сейчас в комбинации
111000101, которая является последней в переборе комбинаций вида
xxxxx0101. По старому алгоритму мы должны вычесть из суммы последние три повторяющихся элемента, вычесть следующий входящий элемент. После этого останется сумма элементов
000000001. Используя массив кумулятивных сумм проверяем является ли недолётом комбинация
111110001, которая даёт максимальную сумму для подмножества комбинаций вида
xxxxx0001. Если недолётом не является, то переходим к первой комбинации проверенного подмножества, то есть к
000010001. Если же был недолёт надо переходить к последней комбинации, которой является комбинация
111000001, снова устанавливая в единички последние три элемента. Что-то мне тут не нравится...

-- 31.01.2018, 16:15 --

B@R5uk в сообщении #1287685 писал(а):

Надо заметить, что кумулятивная сумма для отбрасывания недолётов считается без первого элемента. Это нужно, чтобы не делать лишних вычислений в теле цикла.

Вот чего не хватает! Проверку надо делать до вычитания первых трёх элементов, тогда не надо лишний раз сбрасывать и устанавливать флаги вхождения. То есть кумулятивные суммы должны быть без первых повторяющихся элементов. Однако тогда сначала надо вычесть отбрасываемый на этом шаге элемент... Тоже загвоздка в том, можно ли это сделать.

[grizzly]

B@R5uk
Алгоритм arseniiv на примере из Вашего предыдущего сообщения даёт 37 строк (vs Ваши 120). И я там не нашёл ни одной лишней строки. Типа такого, как здесь:

B@R5uk в сообщении #1288692 писал(а):

1111111000 -> 10 (11)

После этой строки в Вашем листинге проверятся ещё 13 заведомо ненужных строк (поскольку все они, очевидно, дают меньшую сумму). Вы возразили ранее, что учитывать это себе дороже, но такой аргумент напрочь убивается работающим алгоритмом.

Вполне может быть, что за то время, которое Вы планируете потратить на оптимизацию Вашего алгоритма, можно было бы разобрать несколько строк программы на другом языке (заодно и польза дополнительная была бы :) Ну, или можно подождать, пока у кого-то появится мотивация разобраться в Вашем алгоритме и помочь его усовершенствовать.

[B@R5uk]

grizzly в сообщении #1288874 писал(а):

После этой строки в Вашем листинге проверятся ещё 13 заведомо ненужных строк (поскольку все они, очевидно, дают меньшую сумму).

Потому что в последнем алгоритме я ещё не реализовал пропуск недолётов. Вот сейчас над этим думаю.

[arseniiv]

B@R5uk в сообщении #1288692 писал(а):

Процесс подсчёта количества пропущенных комбинаций кажется на столько не тривиальным, что почти невозможным.

А это зачем? Ведь если посчитать количество непропущеных, а количество всех посчитать ещё проще, можно найти и первое.

grizzly в сообщении #1288874 писал(а):

можно было бы разобрать несколько строк программы на другом языке

Кстати, этот язык на текущей стадии развития компилируется и в JS, и в код для JVM — может быть релевантно B@R5uk, раз сейчас он пишет на Java.

grizzly в сообщении #1288874 писал(а):

Ну, или можно подождать, пока у кого-то появится мотивация разобраться в Вашем алгоритме и помочь его усовершенствовать.

У меня есть мотивация порекламировать подход, опирающийся на обход дерева и пропуски поддеревьев, а не перебор комбинаций (соответствующих только листьям дерева) и пропуск множеств комбинаций — итог один и тот же, но в первом, по-моему, проще понять состояние алгоритма и что когда делать (когда вычитать, когда не вычитать) — причислю это дополнительным состояниям нахождения в узле дерева, не являющемся листом.

[B@R5uk]

arseniiv в сообщении #1288916 писал(а):

А это зачем? Ведь если посчитать количество непропущеных, а количество всех посчитать ещё проще, можно найти и первое.

Для статистики. То, как вы говорите, разумеется, тоже можно сделать, но это подход не позволит отличить какие пропуски сделаны по превышению суммы, а какие — по недобору до нужной суммы.

arseniiv в сообщении #1288916 писал(а):

...подход, опирающийся на обход дерева и пропуски поддеревьев, а не перебор комбинаций...

А в чём суть первого и отличие его от второго? Порядок перебора будет тот же самый? Если нет, то я сомневаюсь, что он будет более эффективным.

[arseniiv]

B@R5uk в сообщении #1288925 писал(а):

То, как вы говорите, разумеется, тоже можно сделать, но это подход не позволит отличить какие пропуски сделаны по превышению суммы, а какие — по недобору до нужной суммы.

Понял. Хотя я не вижу ничего плохого в том, чтобы использовать менее оптимизированный алгоритм, где считать проще, для статистики, и не пытаться возложить эту функцию на более оптимизированный, в котором, в конце концов, она будет, как правило, и не нужна.

B@R5uk в сообщении #1288925 писал(а):

А в чём суть первого и отличие его от второго? Порядок перебора будет тот же самый? Если нет, то я сомневаюсь, что он будет более эффективным.

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

Порядок обхода, в принципе, может быть разным. Я выбрал как у вас, от бо́льших чисел вхождений элементов к меньшим, но разницы не должно быть, если сделать наоборот — просто находить наименьшее число вхождений добавленного к префиксу элемента, наверно, не так прозрачно, как находить наибольшее в исходном.

[B@R5uk]

arseniiv в сообщении #1288932 писал(а):

но разницы не должно быть, если сделать наоборот

С этим то я согласен, у меня вообще в самом первом алгоритме можно было обрабатывать любые несортированные множества чисел. А в том, что делаю сейчас они должны быть сгруппированы так, чтобы совпадающие значения соседствовали (иначе будут повторы, как в первом случае).

То есть, я правильно понимаю, что это фактически тот же самый обход, только вещи теперь называются по-другому?

-- 31.01.2018, 19:57 --

arseniiv в сообщении #1288932 писал(а):

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

Я тут подумал, у меня тоже самое, просто это правило вшито в порядок обхода.

-- 31.01.2018, 20:05 --

B@R5uk в сообщении #1288867 писал(а):

Проверку надо делать до вычитания первых трёх элементов, тогда не надо лишний раз сбрасывать и устанавливать флаги вхождения. То есть кумулятивные суммы должны быть без первых повторяющихся элементов. Однако тогда сначала надо вычесть отбрасываемый на этом шаге элемент... Тоже загвоздка в том, можно ли это сделать.

Оказывается, так делать нельзя. Пропуск по недолёту может осуществляться сразу после пропуска по перелёту, а в этом случае отмеченными могут оказаться не все повторы первого элемента. Поэтому просто прибавить к имеющейся сумме предварительно посчитаную кумулятивную сумму без ведущих повторов нельзя, так как к ней ещё надо добавлять недостающие повторы первого элемента. В общем одна морока без системы с переменным основанием.

Наглядный пример:
[1, 1, 1, 1, 2, 2, 2, 3, 4, 4]
[-1, -1, -1, -1, 3, 3, 3, 6, 7, 7]
3

.........
0001011001 -> 9 (11)
0011011001 -> 10 (11)
0111011001 -> 11 (11) Match! overshot skipping
После этой комбинации проверка недолёта осуществляет выбор между этими двумя комбинациями:
0001001001 -> 7 (11)
1111001001 -> 10 (11) и должна переходить ко второй. Но та, от которой осуществляется переход содержит не все повторы первого элемента. Выходов я вижу два. Первый способ: удаление первых элементов, удаление следующего элемента, проверка необходимости пропуска и, если пропуск, снова добавление первых элементов для перехода к следующей итерации, где будет осуществлена аналогичная проверка на возможность очередного пропуска. В этом случае будет много лишних действий установки/удаления (особенно если повторов первого элемента больше половины всего множества элементов). Второй способ: удалить первые повторяющиеся элементы, затем перебором в цикле найти ту комбинацию, начиная с которой недолётов некоторое время не будет. В этом случае нарушается концепция "одна итерация — одна комбинация", за одно в этом цикле могут быть найдено несколько целевых сумм. Плюс надо не забыть про возможность подойти к концу перебора в этом цикле и грамотно обработать эту ситуацию. Дублирование функции из другого места основного цикла.

[arseniiv]

B@R5uk в сообщении #1288946 писал(а):

у меня вообще в самом первом алгоритме можно было обрабатывать любые несортированные множества чисел

А, я не про этот порядок писал. Числа вхождений — это то, что у вас 1 и 0. Порядок элементов по ценам тоже можно сделать, конечно, любым, но тут лучше вашего предложения начинать с более ценных и заканчивать менее ценными трудно что-то придумать.

B@R5uk в сообщении #1288946 писал(а):

То есть, я правильно понимаю, что это фактически тот же самый обход, только вещи теперь называются по-другому?

Важно, что если бы у меня был перебор без оптимизаций, там перебиралось бы не $n_1n_2\cdots n_N$ подмножеств, а $1 + n_1(1 + n_2(\ldots(1 + n_N)\ldots))$ узлов. Это было бы хуже. Однако это позволяет по-другому смотреть на проектируемые алгоритм и код и видеть там другие, скажем даже, точки вставки, вообще деление на блоки и потенциальные рефакторинги. Хотя я писал сразу с учётом оптимизаций-отсечений и оптимизации представления узла — никакого дерева там не появляется, массив да индекс.

[B@R5uk]

B@R5uk в сообщении #1288946 писал(а):

Выходов я вижу два.

Выбрал второй вариант. Итерации главного цикла становятся весомыми, так что итерировать их, когда этого можно не делать — не разумно. Все возникающие проблемы решил отказавшись от возможности найти совпадение в процессе отброса недолётов. Как следствие чуть большее число комбинаций будет перебираться перед обнаружением совпадения, в котором есть сумма нескольких подряд идущих элементов, начиная с самого первого. Не сильно страшно, так как это не очень часто происходит, да и лишних комбинаций в этом случае перебирается не так уж и много.

Код получился такой:

Используется синтаксис Java

import java.util.*;

public class StudySubsetSearch15 {
        
        private static final Random rng = new Random();
        private static final int maxRand = 5;
        private static final int size = 12;
        private static final int[] values = new int[size];
        private static final int[] cumulativeSums = new int[size];
        private static final int[] entryFlags = new int[size];
        private static final int[] nextEntryReference = new int[size];
        private static final int[] previousGroupReference = new int[size];
        private static int frontRepetitions, index, nextEntryIndex;
        private static int sum, tagetSum;
        
        public static void main(String[] args) {
                int n, value, lastValue, previousEntryIndex;
                int repetitions, subsetsNumber, subsetCount, matchCount;
                boolean isFlagged;
                for (n = 0; size / 4 > n; ++n) {
                        values[n] = 1 + rng.nextInt(4 * maxRand);
                }
                for (; size > n; ++n) {
                        values[n] = 1 + rng.nextInt(maxRand);
                }
                Arrays.sort(values);
                
                index = -1;
                previousGroupReference[0] = index;
                lastValue = values[0];
                sum = lastValue;
                cumulativeSums[0] = sum;
                isFlagged = true;
                repetitions = 0;
                subsetsNumber = 1;
                for (n = 1; size > n; ++n) {
                        value = values[n];
                        sum += value;
                        cumulativeSums[n] = sum;
                        if (lastValue != value) {
                                index = n - 1;
                                subsetsNumber *= repetitions + 2;
                                if (isFlagged) {
                                        frontRepetitions = repetitions;
                                        isFlagged = false;
                                }
                                repetitions = 0;
                        } else {
                                ++repetitions;
                        }
                        previousGroupReference[n] = index;
                        lastValue = value;
                }
                if (isFlagged) {
                        frontRepetitions = repetitions;
                }
                subsetsNumber *= repetitions + 2;
                tagetSum = sum / 3 + rng.nextInt(maxRand);
                
                System.out.println(Arrays.toString(values));
                System.out.println(Arrays.toString(cumulativeSums));
                System.out.println(Arrays.toString(previousGroupReference));
                System.out.println(frontRepetitions);
                System.out.println();
                
                nextEntryIndex = size;
                index = size - 1;
                sum = 0;
                subsetCount = 0;
                matchCount = 0;
                while (true) {
                        display(entryFlags, sum, tagetSum);
                        ++subsetCount;
                        if (tagetSum <= sum) {
                                if (tagetSum == sum) {
                                        System.out.print(" Match!");
                                        ++matchCount;
                                } else {
                                        System.out.print("       ");
                                }
                                isFlagged = true;
                        } else {
                                System.out.print("       ");
                                isFlagged = false;
                        }
                        if (-1 == index) {
                                isFlagged = true;
                        } else if (isFlagged) {
                                System.out.print(" overshot skipping");
                                previousEntryIndex = previousGroupReference[nextEntryIndex];
                                if (-1 != previousEntryIndex) {
                                        entryFlags[nextEntryIndex] = 0;
                                        sum -= values[nextEntryIndex];
                                        nextEntryIndex = nextEntryReference[nextEntryIndex];
                                        index = previousEntryIndex;
                                        isFlagged = false;
                                }
                        }
                        if (isFlagged) {
                                do {
                                        ++index;
                                        entryFlags[index] = 0;
                                        sum -= values[index];
                                } while (frontRepetitions > index);
                                nextEntryIndex = nextEntryReference[frontRepetitions];
                                isFlagged = true;
                                while (true) {
                                        if (size == nextEntryIndex) {
                                                isFlagged = true;
                                                break;
                                        }
                                        entryFlags[nextEntryIndex] = 0;
                                        sum -= values[nextEntryIndex];
                                        index = previousGroupReference[nextEntryIndex];
                                        nextEntryIndex = nextEntryReference[nextEntryIndex];
                                        if (tagetSum <= cumulativeSums[index] + sum) {
                                                isFlagged = false;
                                                break;
                                        }
                                        if (isFlagged) {
                                                System.out.print(" undeshot skipping");
                                                isFlagged = false;
                                        }
                                }
                                if (isFlagged) {
                                        System.out.println(" end");
                                        break;
                                }
                        }
                        entryFlags[index] = 1;
                        sum += values[index];
                        nextEntryReference[index] = nextEntryIndex;
                        nextEntryIndex = index;
                        --index;
                        System.out.println();
                }
                System.out.println();
                System.out.print("Subsets found: ");
                System.out.println(matchCount);
                System.out.print("Subsets searched: ");
                System.out.println(subsetCount);
                System.out.print("Subsets total number: ");
                System.out.println(subsetsNumber);
        }
        
        private static void display(int[] array, int sum, int tagetSum) {
                int n, size;
                size = array.length;
                for (n = 0; size > n; ++n) {
                        System.out.print(array[n]);
                }
                System.out.print(" -> ");
                System.out.print(String.format("%2d", sum));
                System.out.print(" (");
                System.out.print(tagetSum);
                System.out.print(")");
        }
}

Используется синтаксис Text

[1, 1, 1, 1, 4, 4, 5, 5, 5, 9, 18, 20]
[1, 2, 3, 4, 8, 12, 17, 22, 27, 36, 54, 74]
[-1, -1, -1, -1, 3, 3, 5, 5, 5, 8, 9, 10]
3

000000000000 ->  0 (25)       
000000000001 -> 20 (25)       
000000000011 -> 38 (25)        overshot skipping
000000000101 -> 29 (25)        overshot skipping
000000001001 -> 25 (25) Match! overshot skipping
000001000001 -> 24 (25)       
000011000001 -> 28 (25)        overshot skipping
000101000001 -> 25 (25) Match! overshot skipping undeshot skipping
000000000010 -> 18 (25)       
000000000110 -> 27 (25)        overshot skipping
000000001010 -> 23 (25)       
000000011010 -> 28 (25)        overshot skipping
000001001010 -> 27 (25)        overshot skipping
000100001010 -> 24 (25)       
001100001010 -> 25 (25) Match! overshot skipping
000001000010 -> 22 (25)       
000011000010 -> 26 (25)        overshot skipping
000101000010 -> 23 (25)       
001101000010 -> 24 (25)       
011101000010 -> 25 (25) Match! overshot skipping undeshot skipping
000000000100 ->  9 (25)       
000000001100 -> 14 (25)       
000000011100 -> 19 (25)       
000000111100 -> 24 (25)       
000001111100 -> 28 (25)        overshot skipping
000100111100 -> 25 (25) Match! overshot skipping
000001011100 -> 23 (25)       
000011011100 -> 27 (25)        overshot skipping
000101011100 -> 24 (25)       
001101011100 -> 25 (25) Match! overshot skipping undeshot skipping
000001001100 -> 18 (25)       
000011001100 -> 22 (25)       
000111001100 -> 23 (25)       
001111001100 -> 24 (25)       
011111001100 -> 25 (25) Match! overshot skipping undeshot skipping
000000001000 ->  5 (25)       
000000011000 -> 10 (25)       
000000111000 -> 15 (25)       
000001111000 -> 19 (25)       
000011111000 -> 23 (25)       
000111111000 -> 24 (25)       
001111111000 -> 25 (25) Match! overshot skipping undeshot skipping end

Subsets found: 8
Subsets searched: 42
Subsets total number: 480

Используется синтаксис Text

[1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 7, 15]
[1, 2, 4, 6, 9, 12, 16, 20, 25, 30, 37, 52]
[-1, -1, 1, 1, 3, 3, 5, 5, 7, 7, 9, 10]
1

000000000000 ->  0 (21)       
000000000001 -> 15 (21)       
000000000011 -> 22 (21)        overshot skipping
000000000101 -> 20 (21)       
000000001101 -> 25 (21)        overshot skipping
000000010101 -> 24 (21)        overshot skipping
000001000101 -> 23 (21)        overshot skipping
000100000101 -> 22 (21)        overshot skipping
010000000101 -> 21 (21) Match! overshot skipping
000000010001 -> 19 (21)       
000000110001 -> 23 (21)        overshot skipping
000001010001 -> 22 (21)        overshot skipping
000100010001 -> 21 (21) Match! overshot skipping
010000010001 -> 20 (21)       
110000010001 -> 21 (21) Match!
000001000001 -> 18 (21)       
000011000001 -> 21 (21) Match! overshot skipping
000101000001 -> 20 (21)       
001101000001 -> 22 (21)        overshot skipping
010101000001 -> 21 (21) Match! overshot skipping undeshot skipping
000100000001 -> 17 (21)       
001100000001 -> 19 (21)       
011100000001 -> 20 (21)       
111100000001 -> 21 (21) Match! undeshot skipping
000000000010 ->  7 (21)       
000000000110 -> 12 (21)       
000000001110 -> 17 (21)       
000000011110 -> 21 (21) Match! overshot skipping
000001001110 -> 20 (21)       
000011001110 -> 23 (21)        overshot skipping
000101001110 -> 22 (21)        overshot skipping
010001001110 -> 21 (21) Match! overshot skipping
000100001110 -> 19 (21)       
001100001110 -> 21 (21) Match! overshot skipping
010100001110 -> 20 (21)       
110100001110 -> 21 (21) Match! undeshot skipping
000000010110 -> 16 (21)       
000000110110 -> 20 (21)       
000001110110 -> 23 (21)        overshot skipping
000100110110 -> 22 (21)        overshot skipping
010000110110 -> 21 (21) Match! overshot skipping
000001010110 -> 19 (21)       
000011010110 -> 22 (21)        overshot skipping
000101010110 -> 21 (21) Match! overshot skipping
010001010110 -> 20 (21)       
110001010110 -> 21 (21) Match!
000100010110 -> 18 (21)       
001100010110 -> 20 (21)       
011100010110 -> 21 (21) Match! overshot skipping undeshot skipping
000001000110 -> 15 (21)       
000011000110 -> 18 (21)       
000111000110 -> 20 (21)       
001111000110 -> 22 (21)        overshot skipping
010111000110 -> 21 (21) Match! overshot skipping undeshot skipping
000101000110 -> 17 (21)       
001101000110 -> 19 (21)       
011101000110 -> 20 (21)       
111101000110 -> 21 (21) Match! undeshot skipping
000000010010 -> 11 (21)       
000000110010 -> 15 (21)       
000001110010 -> 18 (21)       
000011110010 -> 21 (21) Match! overshot skipping
000101110010 -> 20 (21)       
001101110010 -> 22 (21)        overshot skipping
010101110010 -> 21 (21) Match! overshot skipping undeshot skipping
000100110010 -> 17 (21)       
001100110010 -> 19 (21)       
011100110010 -> 20 (21)       
111100110010 -> 21 (21) Match! undeshot skipping
000001010010 -> 14 (21)       
000011010010 -> 17 (21)       
000111010010 -> 19 (21)       
001111010010 -> 21 (21) Match! overshot skipping
010111010010 -> 20 (21)       
110111010010 -> 21 (21) Match! undeshot skipping
000000000100 ->  5 (21)       
000000001100 -> 10 (21)       
000000011100 -> 14 (21)       
000000111100 -> 18 (21)       
000001111100 -> 21 (21) Match! overshot skipping
000100111100 -> 20 (21)       
001100111100 -> 22 (21)        overshot skipping
010100111100 -> 21 (21) Match! overshot skipping undeshot skipping
000001011100 -> 17 (21)       
000011011100 -> 20 (21)       
000111011100 -> 22 (21)        overshot skipping
010011011100 -> 21 (21) Match! overshot skipping
000101011100 -> 19 (21)       
001101011100 -> 21 (21) Match! overshot skipping
010101011100 -> 20 (21)       
110101011100 -> 21 (21) Match! undeshot skipping
000001001100 -> 13 (21)       
000011001100 -> 16 (21)       
000111001100 -> 18 (21)       
001111001100 -> 20 (21)       
011111001100 -> 21 (21) Match! overshot skipping undeshot skipping
000000010100 ->  9 (21)       
000000110100 -> 13 (21)       
000001110100 -> 16 (21)       
000011110100 -> 19 (21)       
000111110100 -> 21 (21) Match! overshot skipping
010011110100 -> 20 (21)       
110011110100 -> 21 (21) Match!
000101110100 -> 18 (21)       
001101110100 -> 20 (21)       
011101110100 -> 21 (21) Match! overshot skipping undeshot skipping
000001010100 -> 12 (21)       
000011010100 -> 15 (21)       
000111010100 -> 17 (21)       
001111010100 -> 19 (21)       
011111010100 -> 20 (21)       
111111010100 -> 21 (21) Match! undeshot skipping end

Subsets found: 31
Subsets searched: 112
Subsets total number: 972

Используется синтаксис Text

[1, 1, 2, 2, 3, 4, 4, 4, 5, 10, 16, 19]
[1, 2, 4, 6, 9, 13, 17, 21, 26, 36, 52, 71]
[-1, -1, 1, 1, 3, 4, 4, 4, 7, 8, 9, 10]
1

000000000000 ->  0 (24)       
000000000001 -> 19 (24)       
000000000011 -> 35 (24)        overshot skipping
000000000101 -> 29 (24)        overshot skipping
000000001001 -> 24 (24) Match! overshot skipping
000000010001 -> 23 (24)       
000000110001 -> 27 (24)        overshot skipping
000010010001 -> 26 (24)        overshot skipping
000100010001 -> 25 (24)        overshot skipping
010000010001 -> 24 (24) Match! overshot skipping
000010000001 -> 22 (24)       
000110000001 -> 24 (24) Match! overshot skipping
010010000001 -> 23 (24)       
110010000001 -> 24 (24) Match!
000100000001 -> 21 (24)       
001100000001 -> 23 (24)       
011100000001 -> 24 (24) Match! overshot skipping undeshot skipping
000000000010 -> 16 (24)       
000000000110 -> 26 (24)        overshot skipping
000000001010 -> 21 (24)       
000000011010 -> 25 (24)        overshot skipping
000010001010 -> 24 (24) Match! overshot skipping
000100001010 -> 23 (24)       
001100001010 -> 25 (24)        overshot skipping
010100001010 -> 24 (24) Match! overshot skipping undeshot skipping
000000010010 -> 20 (24)       
000000110010 -> 24 (24) Match! overshot skipping
000010010010 -> 23 (24)       
000110010010 -> 25 (24)        overshot skipping
010010010010 -> 24 (24) Match! overshot skipping
000100010010 -> 22 (24)       
001100010010 -> 24 (24) Match! overshot skipping
010100010010 -> 23 (24)       
110100010010 -> 24 (24) Match! undeshot skipping
000010000010 -> 19 (24)       
000110000010 -> 21 (24)       
001110000010 -> 23 (24)       
011110000010 -> 24 (24) Match! overshot skipping undeshot skipping
000000000100 -> 10 (24)       
000000001100 -> 15 (24)       
000000011100 -> 19 (24)       
000000111100 -> 23 (24)       
000001111100 -> 27 (24)        overshot skipping
000010111100 -> 26 (24)        overshot skipping
000100111100 -> 25 (24)        overshot skipping
010000111100 -> 24 (24) Match! overshot skipping
000010011100 -> 22 (24)       
000110011100 -> 24 (24) Match! overshot skipping
010010011100 -> 23 (24)       
110010011100 -> 24 (24) Match!
000100011100 -> 21 (24)       
001100011100 -> 23 (24)       
011100011100 -> 24 (24) Match! overshot skipping undeshot skipping
000010001100 -> 18 (24)       
000110001100 -> 20 (24)       
001110001100 -> 22 (24)       
011110001100 -> 23 (24)       
111110001100 -> 24 (24) Match! undeshot skipping
000000010100 -> 14 (24)       
000000110100 -> 18 (24)       
000001110100 -> 22 (24)       
000011110100 -> 25 (24)        overshot skipping
000101110100 -> 24 (24) Match! overshot skipping
010001110100 -> 23 (24)       
110001110100 -> 24 (24) Match!
000010110100 -> 21 (24)       
000110110100 -> 23 (24)       
001110110100 -> 25 (24)        overshot skipping
010110110100 -> 24 (24) Match! overshot skipping undeshot skipping
000100110100 -> 20 (24)       
001100110100 -> 22 (24)       
011100110100 -> 23 (24)       
111100110100 -> 24 (24) Match! undeshot skipping
000000001000 ->  5 (24)       
000000011000 ->  9 (24)       
000000111000 -> 13 (24)       
000001111000 -> 17 (24)       
000011111000 -> 20 (24)       
000111111000 -> 22 (24)       
001111111000 -> 24 (24) Match! overshot skipping
010111111000 -> 23 (24)       
110111111000 -> 24 (24) Match! undeshot skipping end

Subsets found: 23
Subsets searched: 82
Subsets total number: 1152

Вроде считает правильно, хотя это тоже надо бы как-то потестить...

[grizzly]

B@R5uk в сообщении #1288985 писал(а):

надо бы как-то потестить...

Пожалуйста: результаты первых двух тестов совпали с результатами от arseniiv, но строк в Вашем листинге меньше (в первом чуть, а во втором почти на 30%). Правда, не уверен, что подробность листингов идентична (лень углубляться). В любом случае в Вашем листинге я не замечаю теперь прошлых проблем. Хотя вижу, что и в нём есть ещё куда оптимизироваться :) (Но на этот раз я уже не уверен, что это необходимо.)

[B@R5uk]

grizzly в сообщении #1288999 писал(а):

Правда, не уверен, что подробность листингов идентична

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

-- 01.02.2018, 10:04 --

grizzly в сообщении #1288999 писал(а):

Хотя вижу, что и в нём есть ещё куда оптимизироваться

Например?

[grizzly]

B@R5uk в сообщении #1289046 писал(а):

Например?

Ну вот здесь, например:

B@R5uk в сообщении #1288985 писал(а):

000001000001 -> 24 (25)
...
000000000010 -> 18 (25)

После недолётной комбинации появляется ещё меньшая. Я не говорю, что это обязательно нужно оптимизировать и не уверен, что это просто (хотя не исключаю, что использование упомянутых выше деревьев может помочь). Просто я привык считать, что те оптимизации, которые можно учесть при ручном переборе, тем более нужно учитывать при машинном. (Кстати, в сторону перелёта я подобных ситуаций не наблюдаю, что даёт мне повод говорить об этом.

PS. А вообще я не программист, просто сочувствующий. И кроме как поддержание интересного разговора никаких целей не преследую

[B@R5uk]

Переработал свой алгоритм в конечный автомат на четыре состояния.

0) В нулевом осуществляется сдвиг единички влево, то есть удаление предыдущего элемента и добавление текущего. В это состояние можно попасть, если на предыдущем шаге был перелёт.
1) В первом состоянии просто добавляется текущий элемент. После выполнения итерации в этих состояниях осуществляется проверка на перелёт и на достижение самого первого элемента. В последнем случае осуществляется переход ко
2) второму состоянию, которое является промежуточным перед третьим и в котором удаляются из суммы все повторы первого элемента.
3) В третьем состоянии осуществляется поочерёдное удаление уже добавленных в сумму элементов и проверка на недолёт. Поскольку эти проверки теперь делаются в основном цикле по одной на итерацию, то я вернул возможность поймать нужную сумму в процессе проверок, сразу выдать её и пропустить обработку целой пачки состояний.

Код получился такой:

Используется синтаксис Java

import java.util.*;

public class StudySubsetSearch16 {
        
        private static final Random rng = new Random();
        private static final int maxRand = 4;
        private static final int size = 12;
        private static final int[] values = new int[size];
        private static final int[] cumulativeSums = new int[size];
        private static final int[] entryFlags = new int[size];
        private static final int[] entryToTheRight = new int[size];
        private static final int[] entryToTheLeft = new int[size];
        private static int firstRepeats, state, index, nextEntryIndex;
        private static int sum, tagetSum;
        
        public static void main(String[] args) {
                int n, value, lastValue, previousEntryIndex, totalSum;
                int repetitions, subsetsNumber, matchCount, iterationCount;
                boolean isFlagged;
                for (n = 0; size / 4 > n; ++n) {
                        values[n] = 2 + maxRand + rng.nextInt(4 * maxRand);
                }
                for (; size > n; ++n) {
                        values[n] = 2 + rng.nextInt(maxRand);
                }
                Arrays.sort(values);
                
                index = -1;
                entryToTheLeft[0] = index;
                lastValue = values[0];
                sum = lastValue;
                cumulativeSums[0] = sum;
                isFlagged = true;
                repetitions = 0;
                subsetsNumber = 1;
                for (n = 1; size > n; ++n) {
                        value = values[n];
                        sum += value;
                        cumulativeSums[n] = sum;
                        if (lastValue != value) {
                                index = n - 1;
                                subsetsNumber *= repetitions + 2;
                                if (isFlagged) {
                                        firstRepeats = repetitions;
                                        isFlagged = false;
                                }
                                repetitions = 0;
                        } else {
                                ++repetitions;
                        }
                        entryToTheLeft[n] = index;
                        lastValue = value;
                }
                if (isFlagged) {
                        firstRepeats = repetitions;
                }
                subsetsNumber *= repetitions + 2;
                tagetSum = sum / 3 + rng.nextInt(maxRand);
                
                System.out.println(Arrays.toString(values));
                System.out.println(Arrays.toString(cumulativeSums));
                System.out.println(Arrays.toString(entryToTheLeft));
                System.out.println(firstRepeats);
                System.out.println();
                
                nextEntryIndex = size;
                index = size - 1;
                sum = 0;
                state = 1;
                matchCount = 0;
                iterationCount = 0;
                isFlagged = true;
                while (isFlagged) {
                        switch (state) {
                        case 0:
                                previousEntryIndex = entryToTheLeft[nextEntryIndex];;
                                if (-1 == previousEntryIndex) {
                                        state = 2;
                                        break;
                                }
                                entryFlags[nextEntryIndex] = 0;
                                sum -= values[nextEntryIndex];
                                nextEntryIndex = entryToTheRight[nextEntryIndex];
                                index = previousEntryIndex;
                        case 1:
                                entryFlags[index] = 1;
                                sum += values[index];
                                entryToTheRight[index] = nextEntryIndex;
                                nextEntryIndex = index;
                                --index;
                                display(entryFlags, -1, sum, tagetSum);
                                if (tagetSum <= sum) {
                                        if (tagetSum == sum) {
                                                System.out.println(" Match!");
                                                ++matchCount;
                                        } else {
                                                System.out.println(" Overshot");
                                        }
                                        state = 0;
                                } else {
                                        System.out.println();
                                        state = 1;
                                }
                                if (-1 == index) {
                                        state = 2;
                                }
                                break;
                        case 2:
                                do {
                                        ++index;
                                        entryFlags[index] = 0;
                                        sum -= values[index];
                                } while (firstRepeats > index);
                                nextEntryIndex = entryToTheRight[firstRepeats];
                                state = 3;
                        default:
                                if (size == nextEntryIndex) {
                                        display(entryFlags, -1, sum, tagetSum);
                                        System.out.println(" End");
                                        isFlagged = false;
                                        break;
                                }
                                entryFlags[nextEntryIndex] = 0;
                                sum -= values[nextEntryIndex];
                                index = entryToTheLeft[nextEntryIndex];
                                nextEntryIndex = entryToTheRight[nextEntryIndex];
                                totalSum = cumulativeSums[index] + sum;
                                display(entryFlags, index, totalSum, tagetSum);
                                if (tagetSum > totalSum) {
                                        System.out.println(" Undershot");
                                } else if (tagetSum == totalSum) {
                                        System.out.println(" Match!");
                                        ++matchCount;
                                } else {
                                        System.out.println();
                                        state = 1;
                                }
                        }
                        ++iterationCount;
                }
                System.out.println();
                System.out.print("Subsets found: ");
                System.out.println(matchCount);
                System.out.print("Itrations made: ");
                System.out.println(iterationCount);
                System.out.print("Subsets total number: ");
                System.out.println(subsetsNumber);
        }
        
        private static void display(int[] array, int index, int sum, int tagetSum) {
                int n, size;
                size = array.length;
                for (n = 0; index >= n; ++n) {
                        System.out.print("x");
                }
                for (; size > n; ++n) {
                        System.out.print(array[n]);
                }
                System.out.print(" -> ");
                System.out.print(String.format("%2d", sum));
                System.out.print(" (");
                System.out.print(tagetSum);
                System.out.print(")");
        }
}

Результаты он выдаёт приблизительно такие:

Используется синтаксис Text

[2, 2, 2, 2, 2, 4, 4, 4, 5, 7, 16, 20]
[2, 4, 6, 8, 10, 14, 18, 22, 27, 34, 50, 70]
[-1, -1, -1, -1, -1, 4, 4, 4, 7, 8, 9, 10]
4

000000000001 -> 20 (23)
000000000011 -> 36 (23) Overshot
000000000101 -> 27 (23) Overshot
000000001001 -> 25 (23) Overshot
000000010001 -> 24 (23) Overshot
000010000001 -> 22 (23)
000110000001 -> 24 (23) Overshot
xxxxxxxxxxx0 -> 50 (23)
000000000010 -> 16 (23)
000000000110 -> 23 (23) Match!
000000001010 -> 21 (23)
000000011010 -> 25 (23) Overshot
000010001010 -> 23 (23) Match!
xxxxxxxx0010 -> 38 (23)
000000010010 -> 20 (23)
000000110010 -> 24 (23) Overshot
000010010010 -> 22 (23)
000110010010 -> 24 (23) Overshot
xxxxx0000010 -> 26 (23)
000010000010 -> 18 (23)
000110000010 -> 20 (23)
001110000010 -> 22 (23)
011110000010 -> 24 (23) Overshot
xxxxxxxxxx00 -> 34 (23)
000000000100 ->  7 (23)
000000001100 -> 12 (23)
000000011100 -> 16 (23)
000000111100 -> 20 (23)
000001111100 -> 24 (23) Overshot
000010111100 -> 22 (23)
000110111100 -> 24 (23) Overshot
xxxxx0011100 -> 26 (23)
000010011100 -> 18 (23)
000110011100 -> 20 (23)
001110011100 -> 22 (23)
011110011100 -> 24 (23) Overshot
xxxxx0001100 -> 22 (23) Undershot
xxxxxxxx0100 -> 29 (23)
000000010100 -> 11 (23)
000000110100 -> 15 (23)
000001110100 -> 19 (23)
000011110100 -> 21 (23)
000111110100 -> 23 (23) Match!
xxxxx0110100 -> 25 (23)
000010110100 -> 17 (23)
000110110100 -> 19 (23)
001110110100 -> 21 (23)
011110110100 -> 23 (23) Match!
xxxxx0010100 -> 21 (23) Undershot
xxxxx0000100 -> 17 (23) Undershot
xxxxxxxxx000 -> 27 (23)
000000001000 ->  5 (23)
000000011000 ->  9 (23)
000000111000 -> 13 (23)
000001111000 -> 17 (23)
000011111000 -> 19 (23)
000111111000 -> 21 (23)
001111111000 -> 23 (23) Match!
xxxxx0111000 -> 23 (23) Match!
xxxxx0011000 -> 19 (23) Undershot
xxxxx0001000 -> 15 (23) Undershot
xxxxxxxx0000 -> 22 (23) Undershot
000000000000 ->  0 (23) End

Subsets found: 6
Itrations made: 72
Subsets total number: 384

Используется синтаксис Text

[2, 2, 3, 3, 4, 4, 5, 5, 5, 8, 9, 17]
[2, 4, 7, 10, 14, 18, 23, 28, 33, 41, 50, 67]
[-1, -1, 1, 1, 3, 3, 5, 5, 5, 8, 9, 10]
1

000000000001 -> 17 (23)
000000000011 -> 26 (23) Overshot
000000000101 -> 25 (23) Overshot
000000001001 -> 22 (23)
000000011001 -> 27 (23) Overshot
000001001001 -> 26 (23) Overshot
000100001001 -> 25 (23) Overshot
010000001001 -> 24 (23) Overshot
xxxxxx000001 -> 35 (23)
000001000001 -> 21 (23)
000011000001 -> 25 (23) Overshot
000101000001 -> 24 (23) Overshot
010001000001 -> 23 (23) Match!
xxxx00000001 -> 27 (23)
000100000001 -> 20 (23)
001100000001 -> 23 (23) Match!
010100000001 -> 22 (23)
110100000001 -> 24 (23) Overshot
xx0000000001 -> 21 (23) Undershot
xxxxxxxxxxx0 -> 50 (23)
000000000010 ->  9 (23)
000000000110 -> 17 (23)
000000001110 -> 22 (23)
000000011110 -> 27 (23) Overshot
000001001110 -> 26 (23) Overshot
000100001110 -> 25 (23) Overshot
010000001110 -> 24 (23) Overshot
xxxxxx000110 -> 35 (23)
000001000110 -> 21 (23)
000011000110 -> 25 (23) Overshot
000101000110 -> 24 (23) Overshot
010001000110 -> 23 (23) Match!
xxxx00000110 -> 27 (23)
000100000110 -> 20 (23)
001100000110 -> 23 (23) Match!
010100000110 -> 22 (23)
110100000110 -> 24 (23) Overshot
xx0000000110 -> 21 (23) Undershot
xxxxxxxxx010 -> 42 (23)
000000001010 -> 14 (23)
000000011010 -> 19 (23)
000000111010 -> 24 (23) Overshot
000001011010 -> 23 (23) Match!
000100011010 -> 22 (23)
001100011010 -> 25 (23) Overshot
010100011010 -> 24 (23) Overshot
xx0000011010 -> 23 (23) Match!
xxxxxx001010 -> 32 (23)
000001001010 -> 18 (23)
000011001010 -> 22 (23)
000111001010 -> 25 (23) Overshot
010011001010 -> 24 (23) Overshot
xxxx01001010 -> 28 (23)
000101001010 -> 21 (23)
001101001010 -> 24 (23) Overshot
010101001010 -> 23 (23) Match!
xx0001001010 -> 22 (23) Undershot
xxxx00001010 -> 24 (23)
000100001010 -> 17 (23)
001100001010 -> 20 (23)
011100001010 -> 22 (23)
111100001010 -> 24 (23) Overshot
xx0100001010 -> 21 (23) Undershot
xx0000001010 -> 18 (23) Undershot
xxxxxx000010 -> 27 (23)
000001000010 -> 13 (23)
000011000010 -> 17 (23)
000111000010 -> 20 (23)
001111000010 -> 23 (23) Match!
010111000010 -> 22 (23)
110111000010 -> 24 (23) Overshot
xx0011000010 -> 21 (23) Undershot
xxxx01000010 -> 23 (23) Match!
xxxx00000010 -> 19 (23) Undershot
xxxxxxxxxx00 -> 41 (23)
000000000100 ->  8 (23)
000000001100 -> 13 (23)
000000011100 -> 18 (23)
000000111100 -> 23 (23) Match!
000001011100 -> 22 (23)
000011011100 -> 26 (23) Overshot
000101011100 -> 25 (23) Overshot
010001011100 -> 24 (23) Overshot
xxxx00011100 -> 28 (23)
000100011100 -> 21 (23)
001100011100 -> 24 (23) Overshot
010100011100 -> 23 (23) Match!
xx0000011100 -> 22 (23) Undershot
xxxxxx001100 -> 31 (23)
000001001100 -> 17 (23)
000011001100 -> 21 (23)
000111001100 -> 24 (23) Overshot
010011001100 -> 23 (23) Match!
xxxx01001100 -> 27 (23)
000101001100 -> 20 (23)
001101001100 -> 23 (23) Match!
010101001100 -> 22 (23)
110101001100 -> 24 (23) Overshot
xx0001001100 -> 21 (23) Undershot
xxxx00001100 -> 23 (23) Match!
xxxxxx000100 -> 26 (23)
000001000100 -> 12 (23)
000011000100 -> 16 (23)
000111000100 -> 19 (23)
001111000100 -> 22 (23)
011111000100 -> 24 (23) Overshot
xx0111000100 -> 23 (23) Match!
xx0011000100 -> 20 (23) Undershot
xxxx01000100 -> 22 (23) Undershot
xxxx00000100 -> 18 (23) Undershot
xxxxxxxxx000 -> 33 (23)
000000001000 ->  5 (23)
000000011000 -> 10 (23)
000000111000 -> 15 (23)
000001111000 -> 19 (23)
000011111000 -> 23 (23) Match!
000101111000 -> 22 (23)
001101111000 -> 25 (23) Overshot
010101111000 -> 24 (23) Overshot
xx0001111000 -> 23 (23) Match!
xxxx00111000 -> 25 (23)
000100111000 -> 18 (23)
001100111000 -> 21 (23)
011100111000 -> 23 (23) Match!
xx0100111000 -> 22 (23) Undershot
xx0000111000 -> 19 (23) Undershot
xxxxxx011000 -> 28 (23)
000001011000 -> 14 (23)
000011011000 -> 18 (23)
000111011000 -> 21 (23)
001111011000 -> 24 (23) Overshot
010111011000 -> 23 (23) Match!
xx0011011000 -> 22 (23) Undershot
xxxx01011000 -> 24 (23)
000101011000 -> 17 (23)
001101011000 -> 20 (23)
011101011000 -> 22 (23)
111101011000 -> 24 (23) Overshot
xx0101011000 -> 21 (23) Undershot
xx0001011000 -> 18 (23) Undershot
xxxx00011000 -> 20 (23) Undershot
xxxxxx001000 -> 23 (23) Match!
xxxxxx000000 -> 18 (23) Undershot
000000000000 ->  0 (23) End

Subsets found: 20
Itrations made: 158
Subsets total number: 864

Используется синтаксис Text

[2, 3, 3, 3, 3, 4, 4, 4, 5, 10, 10, 21]
[2, 5, 8, 11, 14, 18, 22, 26, 31, 41, 51, 72]
[-1, 0, 0, 0, 0, 4, 4, 4, 7, 8, 8, 10]
0

000000000001 -> 21 (26)
000000000011 -> 31 (26) Overshot
000000001001 -> 26 (26) Match!
000000010001 -> 25 (26)
000000110001 -> 29 (26) Overshot
000010010001 -> 28 (26) Overshot
100000010001 -> 27 (26) Overshot
xxxxx0000001 -> 35 (26)
000010000001 -> 24 (26)
000110000001 -> 27 (26) Overshot
100010000001 -> 26 (26) Match!
x00000000001 -> 23 (26) Undershot
xxxxxxxxxxx0 -> 51 (26)
000000000010 -> 10 (26)
000000000110 -> 20 (26)
000000001110 -> 25 (26)
000000011110 -> 29 (26) Overshot
000010001110 -> 28 (26) Overshot
100000001110 -> 27 (26) Overshot
xxxxxxxx0110 -> 46 (26)
000000010110 -> 24 (26)
000000110110 -> 28 (26) Overshot
000010010110 -> 27 (26) Overshot
100000010110 -> 26 (26) Match!
xxxxx0000110 -> 34 (26)
000010000110 -> 23 (26)
000110000110 -> 26 (26) Match!
100010000110 -> 25 (26)
x00000000110 -> 22 (26) Undershot
xxxxxxxxx010 -> 41 (26)
000000001010 -> 15 (26)
000000011010 -> 19 (26)
000000111010 -> 23 (26)
000001111010 -> 27 (26) Overshot
000010111010 -> 26 (26) Match!
100000111010 -> 25 (26)
xxxxx0011010 -> 33 (26)
000010011010 -> 22 (26)
000110011010 -> 25 (26)
001110011010 -> 28 (26) Overshot
100110011010 -> 27 (26) Overshot
x00010011010 -> 24 (26) Undershot
x00000011010 -> 21 (26) Undershot
xxxxx0001010 -> 29 (26)
000010001010 -> 18 (26)
000110001010 -> 21 (26)
001110001010 -> 24 (26)
011110001010 -> 27 (26) Overshot
101110001010 -> 26 (26) Match!
x00110001010 -> 23 (26) Undershot
x00010001010 -> 20 (26) Undershot
x00000001010 -> 17 (26) Undershot
xxxxxxxx0010 -> 36 (26)
000000010010 -> 14 (26)
000000110010 -> 18 (26)
000001110010 -> 22 (26)
000011110010 -> 25 (26)
000111110010 -> 28 (26) Overshot
100011110010 -> 27 (26) Overshot
x00001110010 -> 24 (26) Undershot
xxxxx0110010 -> 32 (26)
000010110010 -> 21 (26)
000110110010 -> 24 (26)
001110110010 -> 27 (26) Overshot
100110110010 -> 26 (26) Match!
x00010110010 -> 23 (26) Undershot
x00000110010 -> 20 (26) Undershot
xxxxx0010010 -> 28 (26)
000010010010 -> 17 (26)
000110010010 -> 20 (26)
001110010010 -> 23 (26)
011110010010 -> 26 (26) Match!
101110010010 -> 25 (26)
x00110010010 -> 22 (26) Undershot
x00010010010 -> 19 (26) Undershot
x00000010010 -> 16 (26) Undershot
xxxxx0000010 -> 24 (26) Undershot
xxxxxxxxx000 -> 31 (26)
000000001000 ->  5 (26)
000000011000 ->  9 (26)
000000111000 -> 13 (26)
000001111000 -> 17 (26)
000011111000 -> 20 (26)
000111111000 -> 23 (26)
001111111000 -> 26 (26) Match!
100111111000 -> 25 (26)
x00011111000 -> 22 (26) Undershot
x00001111000 -> 19 (26) Undershot
xxxxx0111000 -> 27 (26)
000010111000 -> 16 (26)
000110111000 -> 19 (26)
001110111000 -> 22 (26)
011110111000 -> 25 (26)
111110111000 -> 27 (26) Overshot
x01110111000 -> 24 (26) Undershot
x00110111000 -> 21 (26) Undershot
x00010111000 -> 18 (26) Undershot
x00000111000 -> 15 (26) Undershot
xxxxx0011000 -> 23 (26) Undershot
xxxxx0001000 -> 19 (26) Undershot
xxxxxxxx0000 -> 26 (26) Match!
000000000000 ->  0 (26) End

Subsets found: 10
Itrations made: 102
Subsets total number: 480

-- 01.02.2018, 13:42 --

grizzly в сообщении #1289054 писал(а):

После недолётной комбинации появляется ещё меньшая.

Ну, между ними есть и перелётные комбинации, так что я бы не сказал, что эти две вообще хоть как-то связаны. Даже больше, первая принадлежит той половине комбинаций, в которую входит последний элемент, а вторая — в которую не входит.

grizzly в сообщении #1289054 писал(а):

И кроме как поддержание интересного разговора никаких целей не преследую

На самом деле для меня и это очень важно. Собеседник, который не понимает в вопросе, порой может оказаться лучше любого Знайки, потому что когда пытаешь объяснить в подробностях что и зачем делаешь, то во-первых сам начинаешь лучше понимать, что же именно делаешь, а во-вторых, часто бывает так, что замечаешь какую-то какую-нибудь мелкую ошибку или ВНЕЗАПНО приходит озарение, как сделать ещё лучше. Ну и разговор может быть просто стимулом двигаться дальше.


Алсо, написание этого алгоритма вызывает у меня жуткое чувство, что я создаю программу для какого-нибудь брэйнфака или другого языка Тьюринговой трясины.

-- 01.02.2018, 13:45 --

Теперь надо бы создать отдельный функциональный класс, который решает поставленную задачу без всяких статистик и использовать его для по-настоящему жёсткого теста алгоритма.

[arseniiv]

А ещё используйте enum для переменной state, а то магические константы.

[B@R5uk]

arseniiv в сообщении #1289163 писал(а):

А ещё используйте enum для переменной state

Вот так?

Вызывающий код:

Используется синтаксис Java

import java.util.*;

public class StudySubsetSearch17 {
        
        private static final Random rng = new Random();
        private static final int maxRand = 4;
        private static final int size = 20;
        
        private static SubsetsFinder finder;
        
        public static void main(String[] args) {
                int[] values, result;
                int n, sum, tagetSum;
                int matchCount, entriesNumber;
                boolean isFlagged;
                values = new int[size];
                for (n = 0; size / 4 > n; ++n) {
                        values[n] = 2 + maxRand + rng.nextInt(4 * maxRand);
                }
                for (; size > n; ++n) {
                        values[n] = 2 + rng.nextInt(maxRand);
                }
                Arrays.sort(values);
                
                sum = 0;
                for (n = 0; size > n; ++n) {
                        sum += values[n];
                }
                tagetSum = sum / 3 + rng.nextInt(maxRand);
                
                System.out.println(Arrays.toString(values));
                System.out.println();
                
                matchCount = 0;
                finder = new SubsetsFinder(values, tagetSum);
                result = new int[size];
                while (true) {
                        entriesNumber = finder.findNext(result);
                        if (-1 == entriesNumber) {
                                break;
                        }
                        for (n = 0; size > n; ++n) {
                                System.out.print(result[n]);
                        }
                        System.out.print(" -> ");
                        System.out.print(tagetSum);
                        System.out.print(" = ");
                        isFlagged = false;
                        for (n = 0; size > n; ++n) {
                                if (1 == result[n]) {
                                        if (isFlagged) {
                                                System.out.print(" + ");
                                        } else {
                                                isFlagged = true;
                                        }
                                        System.out.print(values[n]);
                                }
                        }
                        System.out.println();
                        ++matchCount;
                }
                System.out.println();
                System.out.print("Subsets found: ");
                System.out.println(matchCount);
        }
}

Решающий код:

Используется синтаксис Java

import java.util.*;

public class SubsetsFinder {
        private enum State {
                SHIFT, ADD, STEP, REMOVE;
        }
        private int size, tagetSum, sum, entriesCount, firstRepeats, index, nextEntryIndex;
        private int[] values, cumulativeSums;
        private int[] entryToTheLeft, entryToTheRight, entryFlags;
        private State state;
        private boolean isDone;
        
        public SubsetsFinder(int[] values, int tagetSum) {
                int n, value, firstValue, lastValue;
                size = values.length;
                this.tagetSum = tagetSum;
                this.values = Arrays.copyOf(values, size);
                cumulativeSums = new int[size];
                entryToTheLeft = new int[size];
                entryToTheRight = new int[size];
                entryFlags = new int[size];
                sum = 0;
                index = -1;
                lastValue = 1;
                firstRepeats = -1;
                firstValue = values[0];
                for (n = 0; size > n; ++n) {
                        value = values[n];
                        if (lastValue > value) {
                                throw new IllegalArgumentException(
                                                "Input must be nondecreasing positive sequence");
                        }
                        if (lastValue != value) {
                                index = n - 1;
                        }
                        if (firstValue == value) {
                                ++firstRepeats;
                        }
                        sum += value;
                        cumulativeSums[n] = sum;
                        entryToTheLeft[n] = index;
                        lastValue = value;
                }
                sum = 0;
                state = State.ADD;
                entriesCount = 0;
                nextEntryIndex = size;
                index = size - 1;
        }
        
        public int findNext(int[] result) {
                int n, answer, previousEntryIndex, totalSum;
                boolean isActive;
                if (isDone) {
                        return -1;
                }
                isActive = true;
                answer = -1;
                while (isActive) {
                        switch (state) {
                        case SHIFT:
                                previousEntryIndex = entryToTheLeft[nextEntryIndex];;
                                if (-1 == previousEntryIndex) {
                                        state = State.STEP;
                                        break;
                                }
                                entryFlags[nextEntryIndex] = 0;
                                sum -= values[nextEntryIndex];
                                --entriesCount;
                                nextEntryIndex = entryToTheRight[nextEntryIndex];
                                index = previousEntryIndex;
                        case ADD:
                                entryFlags[index] = 1;
                                sum += values[index];
                                ++entriesCount;
                                entryToTheRight[index] = nextEntryIndex;
                                nextEntryIndex = index;
                                --index;
                                if (tagetSum <= sum) {
                                        if (tagetSum == sum) {
                                                answer = entriesCount;
                                                for (n = 0; size > n; ++n) {
                                                        result[n] = entryFlags[n];
                                                }
                                                isActive = false;
                                        }
                                        state = State.SHIFT;
                                } else {
                                        state = State.ADD;
                                }
                                if (-1 == index) {
                                        state = State.STEP;
                                }
                                break;
                        case STEP:
                                do {
                                        ++index;
                                        entryFlags[index] = 0;
                                        sum -= values[index];
                                        --entriesCount;
                                } while (firstRepeats > index);
                                nextEntryIndex = entryToTheRight[firstRepeats];
                                state = State.REMOVE;
                        case REMOVE:
                                if (size == nextEntryIndex) {
                                        answer = -1;
                                        isActive = false;
                                        isDone = true;
                                        break;
                                }
                                entryFlags[nextEntryIndex] = 0;
                                sum -= values[nextEntryIndex];
                                --entriesCount;
                                index = entryToTheLeft[nextEntryIndex];
                                nextEntryIndex = entryToTheRight[nextEntryIndex];
                                totalSum = cumulativeSums[index] + sum;
                                if (tagetSum > totalSum) {
                                } else if (tagetSum == totalSum) {
                                        answer = entriesCount;
                                        for (n = 0; size > n; ++n) {
                                                if (index >= n) {
                                                        result[n] = 1;
                                                        ++answer;
                                                } else {
                                                        result[n] = entryFlags[n];
                                                }
                                        }
                                        isActive = false;
                                } else {
                                        state = State.ADD;
                                }
                        }
                }
                return answer;
        }
}
 

Используется синтаксис Text

[2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6, 7, 7, 16, 18]

00000000010000001101 -> 35 = 3 + 7 + 7 + 18
00000000000010010101 -> 35 = 4 + 6 + 7 + 18
00000000000001100101 -> 35 = 5 + 5 + 7 + 18
10000000010000100101 -> 35 = 2 + 3 + 5 + 7 + 18
10000000000110000101 -> 35 = 2 + 4 + 4 + 7 + 18
00000000110010000101 -> 35 = 3 + 3 + 4 + 7 + 18
10000000000010110001 -> 35 = 2 + 4 + 5 + 6 + 18
00000000110000110001 -> 35 = 3 + 3 + 5 + 6 + 18
00000000010110010001 -> 35 = 3 + 4 + 4 + 6 + 18
10000001110000010001 -> 35 = 2 + 3 + 3 + 3 + 6 + 18
00000000010011100001 -> 35 = 3 + 4 + 5 + 5 + 18
00000000001110100001 -> 35 = 4 + 4 + 4 + 5 + 18
10000000110010100001 -> 35 = 2 + 3 + 3 + 4 + 5 + 18
00000011110000100001 -> 35 = 3 + 3 + 3 + 3 + 5 + 18
10000000011110000001 -> 35 = 2 + 3 + 4 + 4 + 4 + 18
00000001110110000001 -> 35 = 3 + 3 + 3 + 4 + 4 + 18
10000111110000000001 -> 35 = 2 + 3 + 3 + 3 + 3 + 3 + 18
00000000000000101110 -> 35 = 5 + 7 + 7 + 16
10000000010000001110 -> 35 = 2 + 3 + 7 + 7 + 16
10000000000010010110 -> 35 = 2 + 4 + 6 + 7 + 16
00000000110000010110 -> 35 = 3 + 3 + 6 + 7 + 16
10000000000001100110 -> 35 = 2 + 5 + 5 + 7 + 16
00000000010010100110 -> 35 = 3 + 4 + 5 + 7 + 16
00000000001110000110 -> 35 = 4 + 4 + 4 + 7 + 16
10000000110010000110 -> 35 = 2 + 3 + 3 + 4 + 7 + 16
00000011110000000110 -> 35 = 3 + 3 + 3 + 3 + 7 + 16
00000000010001110010 -> 35 = 3 + 5 + 5 + 6 + 16
00000000000110110010 -> 35 = 4 + 4 + 5 + 6 + 16
10000000110000110010 -> 35 = 2 + 3 + 3 + 5 + 6 + 16
10000000010110010010 -> 35 = 2 + 3 + 4 + 4 + 6 + 16
00000001110010010010 -> 35 = 3 + 3 + 3 + 4 + 6 + 16
10000000010011100010 -> 35 = 2 + 3 + 4 + 5 + 5 + 16
00000001110001100010 -> 35 = 3 + 3 + 3 + 5 + 5 + 16
10000000001110100010 -> 35 = 2 + 4 + 4 + 4 + 5 + 16
00000000110110100010 -> 35 = 3 + 3 + 4 + 4 + 5 + 16
10000011110000100010 -> 35 = 2 + 3 + 3 + 3 + 3 + 5 + 16
10000001110110000010 -> 35 = 2 + 3 + 3 + 3 + 4 + 4 + 16
00000111110010000010 -> 35 = 3 + 3 + 3 + 3 + 3 + 4 + 16
10000000010001111100 -> 35 = 2 + 3 + 5 + 5 + 6 + 7 + 7
10000000000110111100 -> 35 = 2 + 4 + 4 + 5 + 6 + 7 + 7
00000000110010111100 -> 35 = 3 + 3 + 4 + 5 + 6 + 7 + 7
00000000011110011100 -> 35 = 3 + 4 + 4 + 4 + 6 + 7 + 7
10000001110010011100 -> 35 = 2 + 3 + 3 + 3 + 4 + 6 + 7 + 7
00000111110000011100 -> 35 = 3 + 3 + 3 + 3 + 3 + 6 + 7 + 7
00000000010111101100 -> 35 = 3 + 4 + 4 + 5 + 5 + 7 + 7
10000001110001101100 -> 35 = 2 + 3 + 3 + 3 + 5 + 5 + 7 + 7
10000000110110101100 -> 35 = 2 + 3 + 3 + 4 + 4 + 5 + 7 + 7
00000011110010101100 -> 35 = 3 + 3 + 3 + 3 + 4 + 5 + 7 + 7
00000001111110001100 -> 35 = 3 + 3 + 3 + 4 + 4 + 4 + 7 + 7
10000111110010001100 -> 35 = 2 + 3 + 3 + 3 + 3 + 3 + 4 + 7 + 7
00011111110000001100 -> 35 = 3 + 3 + 3 + 3 + 3 + 3 + 3 + 7 + 7
00000000001111110100 -> 35 = 4 + 4 + 4 + 5 + 5 + 6 + 7
10000000110011110100 -> 35 = 2 + 3 + 3 + 4 + 5 + 5 + 6 + 7
00000011110001110100 -> 35 = 3 + 3 + 3 + 3 + 5 + 5 + 6 + 7
10000000011110110100 -> 35 = 2 + 3 + 4 + 4 + 4 + 5 + 6 + 7
00000001110110110100 -> 35 = 3 + 3 + 3 + 4 + 4 + 5 + 6 + 7
10000111110000110100 -> 35 = 2 + 3 + 3 + 3 + 3 + 3 + 5 + 6 + 7
10000011110110010100 -> 35 = 2 + 3 + 3 + 3 + 3 + 4 + 4 + 6 + 7
00001111110010010100 -> 35 = 3 + 3 + 3 + 3 + 3 + 3 + 4 + 6 + 7
00000000111111100100 -> 35 = 3 + 3 + 4 + 4 + 4 + 5 + 5 + 7
10000011110011100100 -> 35 = 2 + 3 + 3 + 3 + 3 + 4 + 5 + 5 + 7
00001111110001100100 -> 35 = 3 + 3 + 3 + 3 + 3 + 3 + 5 + 5 + 7
10000001111110100100 -> 35 = 2 + 3 + 3 + 3 + 4 + 4 + 4 + 5 + 7
00000111110110100100 -> 35 = 3 + 3 + 3 + 3 + 3 + 4 + 4 + 5 + 7
10011111110000100100 -> 35 = 2 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 5 + 7
10001111110110000100 -> 35 = 2 + 3 + 3 + 3 + 3 + 3 + 3 + 4 + 4 + 7
00111111110010000100 -> 35 = 3 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 4 + 7
10000001110111110000 -> 35 = 2 + 3 + 3 + 3 + 4 + 4 + 5 + 5 + 6
00000111110011110000 -> 35 = 3 + 3 + 3 + 3 + 3 + 4 + 5 + 5 + 6
00000011111110110000 -> 35 = 3 + 3 + 3 + 3 + 4 + 4 + 4 + 5 + 6
10001111110010110000 -> 35 = 2 + 3 + 3 + 3 + 3 + 3 + 3 + 4 + 5 + 6
00111111110000110000 -> 35 = 3 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 5 + 6
10000111111110010000 -> 35 = 2 + 3 + 3 + 3 + 3 + 3 + 4 + 4 + 4 + 6
00011111110110010000 -> 35 = 3 + 3 + 3 + 3 + 3 + 3 + 3 + 4 + 4 + 6
11111111110000010000 -> 35 = 2 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 6
10000111110111100000 -> 35 = 2 + 3 + 3 + 3 + 3 + 3 + 4 + 4 + 5 + 5
00011111110011100000 -> 35 = 3 + 3 + 3 + 3 + 3 + 3 + 3 + 4 + 5 + 5
00001111111110100000 -> 35 = 3 + 3 + 3 + 3 + 3 + 3 + 4 + 4 + 4 + 5
10111111110010100000 -> 35 = 2 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 4 + 5
10011111111110000000 -> 35 = 2 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 4 + 4 + 4
01111111110110000000 -> 35 = 3 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 4 + 4

Set size: 20
Subsets found: 81

Используется синтаксис Text

[2, 2, 2, 2, 2, 2, 3, 4, 4, 5, 5, 5, 5, 5, 5, 9, 14, 16, 17, 21]

00000010000000100011 -> 46 = 3 + 5 + 17 + 21
00000001100000000011 -> 46 = 4 + 4 + 17 + 21
00001100100000000011 -> 46 = 2 + 2 + 4 + 17 + 21
00111100000000000011 -> 46 = 2 + 2 + 2 + 2 + 17 + 21
00000000000000010101 -> 46 = 9 + 16 + 21
00000000100000100101 -> 46 = 4 + 5 + 16 + 21
00001100000000100101 -> 46 = 2 + 2 + 5 + 16 + 21
00000110100000000101 -> 46 = 2 + 3 + 4 + 16 + 21
00011110000000000101 -> 46 = 2 + 2 + 2 + 3 + 16 + 21
00000100000000011001 -> 46 = 2 + 9 + 14 + 21
00000100100000101001 -> 46 = 2 + 4 + 5 + 14 + 21
00011100000000101001 -> 46 = 2 + 2 + 2 + 5 + 14 + 21
00000011100000001001 -> 46 = 3 + 4 + 4 + 14 + 21
00001110100000001001 -> 46 = 2 + 2 + 3 + 4 + 14 + 21
00111110000000001001 -> 46 = 2 + 2 + 2 + 2 + 3 + 14 + 21
00000100100001110001 -> 46 = 2 + 4 + 5 + 5 + 9 + 21
00011100000001110001 -> 46 = 2 + 2 + 2 + 5 + 5 + 9 + 21
00000011100000110001 -> 46 = 3 + 4 + 4 + 5 + 9 + 21
00001110100000110001 -> 46 = 2 + 2 + 3 + 4 + 5 + 9 + 21
00111110000000110001 -> 46 = 2 + 2 + 2 + 2 + 3 + 5 + 9 + 21
00111101100000010001 -> 46 = 2 + 2 + 2 + 2 + 4 + 4 + 9 + 21
11111100100000010001 -> 46 = 2 + 2 + 2 + 2 + 2 + 2 + 4 + 9 + 21
00000000001111100001 -> 46 = 5 + 5 + 5 + 5 + 5 + 21
00000110000111100001 -> 46 = 2 + 3 + 5 + 5 + 5 + 5 + 21
00000101100011100001 -> 46 = 2 + 4 + 4 + 5 + 5 + 5 + 21
00011100100011100001 -> 46 = 2 + 2 + 2 + 4 + 5 + 5 + 5 + 21
01111100000011100001 -> 46 = 2 + 2 + 2 + 2 + 2 + 5 + 5 + 5 + 21
00001111100001100001 -> 46 = 2 + 2 + 3 + 4 + 4 + 5 + 5 + 21
00111110100001100001 -> 46 = 2 + 2 + 2 + 2 + 3 + 4 + 5 + 5 + 21
11111110000001100001 -> 46 = 2 + 2 + 2 + 2 + 2 + 2 + 3 + 5 + 5 + 21
11111101100000100001 -> 46 = 2 + 2 + 2 + 2 + 2 + 2 + 4 + 4 + 5 + 21
00000000100000010110 -> 46 = 4 + 9 + 16 + 17
00001100000000010110 -> 46 = 2 + 2 + 9 + 16 + 17
00000010000001100110 -> 46 = 3 + 5 + 5 + 16 + 17
00000001100000100110 -> 46 = 4 + 4 + 5 + 16 + 17
00001100100000100110 -> 46 = 2 + 2 + 4 + 5 + 16 + 17
00111100000000100110 -> 46 = 2 + 2 + 2 + 2 + 5 + 16 + 17
00000111100000000110 -> 46 = 2 + 3 + 4 + 4 + 16 + 17
00011110100000000110 -> 46 = 2 + 2 + 2 + 3 + 4 + 16 + 17
01111110000000000110 -> 46 = 2 + 2 + 2 + 2 + 2 + 3 + 16 + 17
00000100100000011010 -> 46 = 2 + 4 + 9 + 14 + 17
00011100000000011010 -> 46 = 2 + 2 + 2 + 9 + 14 + 17
00000000000011101010 -> 46 = 5 + 5 + 5 + 14 + 17
00000110000001101010 -> 46 = 2 + 3 + 5 + 5 + 14 + 17
00000101100000101010 -> 46 = 2 + 4 + 4 + 5 + 14 + 17
00011100100000101010 -> 46 = 2 + 2 + 2 + 4 + 5 + 14 + 17
01111100000000101010 -> 46 = 2 + 2 + 2 + 2 + 2 + 5 + 14 + 17
00001111100000001010 -> 46 = 2 + 2 + 3 + 4 + 4 + 14 + 17
00111110100000001010 -> 46 = 2 + 2 + 2 + 2 + 3 + 4 + 14 + 17
11111110000000001010 -> 46 = 2 + 2 + 2 + 2 + 2 + 2 + 3 + 14 + 17
00000000000111110010 -> 46 = 5 + 5 + 5 + 5 + 9 + 17
00000110000011110010 -> 46 = 2 + 3 + 5 + 5 + 5 + 9 + 17
00000101100001110010 -> 46 = 2 + 4 + 4 + 5 + 5 + 9 + 17
00011100100001110010 -> 46 = 2 + 2 + 2 + 4 + 5 + 5 + 9 + 17
01111100000001110010 -> 46 = 2 + 2 + 2 + 2 + 2 + 5 + 5 + 9 + 17
00001111100000110010 -> 46 = 2 + 2 + 3 + 4 + 4 + 5 + 9 + 17
00111110100000110010 -> 46 = 2 + 2 + 2 + 2 + 3 + 4 + 5 + 9 + 17
11111110000000110010 -> 46 = 2 + 2 + 2 + 2 + 2 + 2 + 3 + 5 + 9 + 17
11111101100000010010 -> 46 = 2 + 2 + 2 + 2 + 2 + 2 + 4 + 4 + 9 + 17
00000000101111100010 -> 46 = 4 + 5 + 5 + 5 + 5 + 5 + 17
00001100001111100010 -> 46 = 2 + 2 + 5 + 5 + 5 + 5 + 5 + 17
00000110100111100010 -> 46 = 2 + 3 + 4 + 5 + 5 + 5 + 5 + 17
00011110000111100010 -> 46 = 2 + 2 + 2 + 3 + 5 + 5 + 5 + 5 + 17
00011101100011100010 -> 46 = 2 + 2 + 2 + 4 + 4 + 5 + 5 + 5 + 17
01111100100011100010 -> 46 = 2 + 2 + 2 + 2 + 2 + 4 + 5 + 5 + 5 + 17
00111111100001100010 -> 46 = 2 + 2 + 2 + 2 + 3 + 4 + 4 + 5 + 5 + 17
11111110100001100010 -> 46 = 2 + 2 + 2 + 2 + 2 + 2 + 3 + 4 + 5 + 5 + 17
00000100000000111100 -> 46 = 2 + 5 + 9 + 14 + 16
00000010100000011100 -> 46 = 3 + 4 + 9 + 14 + 16
00001110000000011100 -> 46 = 2 + 2 + 3 + 9 + 14 + 16
00000100100001101100 -> 46 = 2 + 4 + 5 + 5 + 14 + 16
00011100000001101100 -> 46 = 2 + 2 + 2 + 5 + 5 + 14 + 16
00000011100000101100 -> 46 = 3 + 4 + 4 + 5 + 14 + 16
00001110100000101100 -> 46 = 2 + 2 + 3 + 4 + 5 + 14 + 16
00111110000000101100 -> 46 = 2 + 2 + 2 + 2 + 3 + 5 + 14 + 16
00111101100000001100 -> 46 = 2 + 2 + 2 + 2 + 4 + 4 + 14 + 16
11111100100000001100 -> 46 = 2 + 2 + 2 + 2 + 2 + 2 + 4 + 14 + 16
00000100100011110100 -> 46 = 2 + 4 + 5 + 5 + 5 + 9 + 16
00011100000011110100 -> 46 = 2 + 2 + 2 + 5 + 5 + 5 + 9 + 16
00000011100001110100 -> 46 = 3 + 4 + 4 + 5 + 5 + 9 + 16
00001110100001110100 -> 46 = 2 + 2 + 3 + 4 + 5 + 5 + 9 + 16
00111110000001110100 -> 46 = 2 + 2 + 2 + 2 + 3 + 5 + 5 + 9 + 16
00111101100000110100 -> 46 = 2 + 2 + 2 + 2 + 4 + 4 + 5 + 9 + 16
11111100100000110100 -> 46 = 2 + 2 + 2 + 2 + 2 + 2 + 4 + 5 + 9 + 16
01111111100000010100 -> 46 = 2 + 2 + 2 + 2 + 2 + 3 + 4 + 4 + 9 + 16
00000000011111100100 -> 46 = 5 + 5 + 5 + 5 + 5 + 5 + 16
00000110001111100100 -> 46 = 2 + 3 + 5 + 5 + 5 + 5 + 5 + 16
00000101100111100100 -> 46 = 2 + 4 + 4 + 5 + 5 + 5 + 5 + 16
00011100100111100100 -> 46 = 2 + 2 + 2 + 4 + 5 + 5 + 5 + 5 + 16
01111100000111100100 -> 46 = 2 + 2 + 2 + 2 + 2 + 5 + 5 + 5 + 5 + 16
00001111100011100100 -> 46 = 2 + 2 + 3 + 4 + 4 + 5 + 5 + 5 + 16
00111110100011100100 -> 46 = 2 + 2 + 2 + 2 + 3 + 4 + 5 + 5 + 5 + 16
11111110000011100100 -> 46 = 2 + 2 + 2 + 2 + 2 + 2 + 3 + 5 + 5 + 5 + 16
11111101100001100100 -> 46 = 2 + 2 + 2 + 2 + 2 + 2 + 4 + 4 + 5 + 5 + 16
00000010000111111000 -> 46 = 3 + 5 + 5 + 5 + 5 + 9 + 14
00000001100011111000 -> 46 = 4 + 4 + 5 + 5 + 5 + 9 + 14
00001100100011111000 -> 46 = 2 + 2 + 4 + 5 + 5 + 5 + 9 + 14
00111100000011111000 -> 46 = 2 + 2 + 2 + 2 + 5 + 5 + 5 + 9 + 14
00000111100001111000 -> 46 = 2 + 3 + 4 + 4 + 5 + 5 + 9 + 14
00011110100001111000 -> 46 = 2 + 2 + 2 + 3 + 4 + 5 + 5 + 9 + 14
01111110000001111000 -> 46 = 2 + 2 + 2 + 2 + 2 + 3 + 5 + 5 + 9 + 14
01111101100000111000 -> 46 = 2 + 2 + 2 + 2 + 2 + 4 + 4 + 5 + 9 + 14
11111111100000011000 -> 46 = 2 + 2 + 2 + 2 + 2 + 2 + 3 + 4 + 4 + 9 + 14
00000100011111101000 -> 46 = 2 + 5 + 5 + 5 + 5 + 5 + 5 + 14
00000010101111101000 -> 46 = 3 + 4 + 5 + 5 + 5 + 5 + 5 + 14
00001110001111101000 -> 46 = 2 + 2 + 3 + 5 + 5 + 5 + 5 + 5 + 14
00001101100111101000 -> 46 = 2 + 2 + 4 + 4 + 5 + 5 + 5 + 5 + 14
00111100100111101000 -> 46 = 2 + 2 + 2 + 2 + 4 + 5 + 5 + 5 + 5 + 14
11111100000111101000 -> 46 = 2 + 2 + 2 + 2 + 2 + 2 + 5 + 5 + 5 + 5 + 14
00011111100011101000 -> 46 = 2 + 2 + 2 + 3 + 4 + 4 + 5 + 5 + 5 + 14
01111110100011101000 -> 46 = 2 + 2 + 2 + 2 + 2 + 3 + 4 + 5 + 5 + 5 + 14
00000010111111110000 -> 46 = 3 + 4 + 5 + 5 + 5 + 5 + 5 + 5 + 9
00001110011111110000 -> 46 = 2 + 2 + 3 + 5 + 5 + 5 + 5 + 5 + 5 + 9
00001101101111110000 -> 46 = 2 + 2 + 4 + 4 + 5 + 5 + 5 + 5 + 5 + 9
00111100101111110000 -> 46 = 2 + 2 + 2 + 2 + 64 + 5 + 5 + 5 + 5 + 5 + 9
11111100001111110000 -> 46 = 2 + 2 + 2 + 2 + 2 + 2 + 5 + 5 + 5 + 5 + 5 + 9
00011111100111110000 -> 46 = 2 + 2 + 2 + 3 + 4 + 4 + 5 + 5 + 5 + 5 + 9
01111110100111110000 -> 46 = 2 + 2 + 2 + 2 + 2 + 3 + 4 + 5 + 5 + 5 + 5 + 9
00111101111111100000 -> 46 = 2 + 2 + 2 + 2 + 4 + 4 + 5 + 5 + 5 + 5 + 5 + 5
11111100111111100000 -> 46 = 2 + 2 + 2 + 2 + 2 + 2 + 4 + 5 + 5 + 5 + 5 + 5 + 5
01111111101111100000 -> 46 = 2 + 2 + 2 + 2 + 2 + 3 + 4 + 4 + 5 + 5 + 5 + 5 + 5

Set size: 20
Subsets found: 121

Я тут ещё попробовал один раз поставить 50 элементов. Вывод был очень долгим: нашлось 75 с хвостиком тысяч комбинаций. Но время работы было вполне себе сносным (вывод в файл, думаю, был бы быстрее). Это не перебор в лоб $2^{50}$ комбинаций, который при производительности $10^7$ комбинаций в секунду занял бы более 3,5 лет. Не уверен, правда, что тормознутая Джава осилит такую производительность. В общем, не смотря на экспоненциальную по количеству элементов сложность задачи, скорость работы вполне на уровне. Я думаю даже, сложность линейна по количеству существующих комбинаций (но не уверен в этом).

П.С. Опубликовал код, и только тогда заметил, что случайно забыл break перед case REMOVE: в свиче. А потом понял, что так и надо.