Изменение суммы подмножества - подмножество содержит X элементов

Question

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

Так, например, набор элементов

300: [1,5, 1,34, 3, .25, 2.333, 1.75, .125, .675,2, 4, .75, ....]

X = 5

Y = 6

Алгоритм генерирует:

[2, 2,1,5, .25, .25]
[2, 2, .25, 1.5, .25]
[2, 1.5, 2, .25, .25]
[1,5, 2, 2,.25, .25]
[2, 1.75, .5, .5, 1.25]
[2, 1.75, .5, 1.25, .5]
[2, 1.75, 1.25, .5, .5]
[2, 1.25, .5, .5, 1.75]
[1.25, 2, .5, .5, 1.75]
[.5, 2, .5, 1.25,1,75]
[3, 1, 1, .5, .5]
[1, 3, 1, .5, .5]
[1, 1, 3, .5, .5]
[1, 1, .5, 3, .5]
[1, 1, .5, .5, 3]

и т. Д ....

[2, 2, 1.5, .25, .25] разрешено, и

[2, 1.75, .5, .5, 1.25] - это не то же самое, что [1.25, .5, .5, 1.75, 2].

Я понимаю, что это вариация проблемы Subset Sum, но я не могу найти какие-либо полезные примеры этой вариации где-либо в Интернете.Прямо сейчас мое текущее решение реализует вложенные циклы (количество вложенных циклов определяется значением X). Это прекрасно работает, когда X мало, но быстро становится очень медленным, когда X начинает расти.Любой вклад будет оценен!

Answer 1

Подход состоит в том, чтобы собрать подмножества и проверить, подходит ли длина подмножества и суммы.

При необходимости вы можете переставить подмножества.

function subsetSum(array, sum, items) {

    function iter(taken, index, subsum) {
        if (taken.length === items && subsum === sum) return result.push(taken);
        if (taken.length === items || subsum === sum || index === array.length) return;
        iter([...taken, array[index]], index, subsum + array[index]);
        iter(taken, index + 1, subsum);
    }

    var result = [];

    iter([], 0, 0);
    return result;
}

var result = subsetSum([1.5, 1.34, 3, .25, 2.333, 1.75, .125, .675, 2, 4, .75], 6, 5);

console.log(result.map(a => a.join(' ')));

.as-console-wrapper { max-height: 100% !important; top: 0; }