子集总和变化-子集有X个项目

Question

我正在寻找一种算法，该算法将允许我快速访问（不一定要打印）300个项目集中的每个X项目子集，当将子集中的项目值相加时，等于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]不同。

我意识到这是子集总和问题的一种变体，但我似乎无法在任何在线地方找到这种变体的任何有用示例。现在，我当前的解决方案实现了嵌套循环（嵌套循环的数量由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; }