javascript - 查找总和为目标值的给定大小列表的子集

Question

我参加了一个编码测试，其中一个问题是这样的:给定一个任意长度的整数数组 A，然后是两个数字 N 和 Z，说 A 中是否有 Z(不同的)数字，例如它们的总和是N.

例如(格式为 A N Z):

• 对于 [1,2,3] 5 2，答案是肯定的，因为 2+3=5
• 对于 [1,2,3] 6 2，答案是否定的，因为 A 中没有两个数字可以相加得到 6

我的解决方案(如下)首先枚举 A 中 Z 数的每个(无序)组合，然后对其求和，然后在求和列表中搜索 N。

虽然这个解决方案运行良好(通过了所有测试用例，没有超时)，但我被告知分数太低，无法继续测试。

那么问题来了，有什么可以改进的地方吗？

一个明显的优化是立即计算每个组合的总和，然后在找到与 N 的匹配时停止；但由于我没有遇到时间问题，所以我认为这不是问题所在。什么是更好、更优雅/更高效的解决方案？

function main(a, n, z) {
    var spacea = [], // array of unordered combinations of z integers from a
        space = [], // array of unique sums of combinations from spacea
        res=0; // result (1 or 0)

    // produce combination
    spacea = combo(a,z);

    // put unique sums in space
    spacea.forEach(function(arr) {
        var s = arr.reduce(function(a,b) {
            return a+b;
            });
        if (space.indexOf(s)<0) space.push(s);
        });

    // is n in space?
    res = space.indexOf(n) === -1 ? "NO" :"YES";
    return res;
    }

// produces combinations (outputs array of arrays)                
function combo(a, z) {
    var i,
        r = [],
        head,
        right;
    if (z > a.length || z <= 0) {
        // do nothing, r is already set to []
        }
    else if (a.length === z) {
        r = [a];
        }
    else if (1 === z) {
        // r = array of array of values from a
        a.forEach(function(e) {
            r.push([e]);
            });
        }
    else { // by virtue of above tests, z>1 and z<a.length
        for (i=0; i<a.length-z+1; i++) {
            head = a.slice(i, i+1);
            right = combo(a.slice(i+1), z-1);
            right.forEach(function(e) {
                r.push(head.concat(e));
                });
            }
        }
    return r;
    }

Answer 1

这是 subset sum problem 的变体, 这可以用 Dynamic Programming 来解决以获得更有效的解决方案。

这里的主要区别是您有一个额外的限制 - 必须使用的元素数量。这个额外的限制可以通过添加另一个变量(维度)来处理——已经使用的元素的数量。

递归公式(您将从中构建 DP 解决方案)应该是:

D(0,0,0) = true
D(i,k,x) = false    if i < 0 or k < 0
D(i,k,x) = D(i-1, k, x) OR D(i-1, k-1, x - arr[i])

在上面，D(i,k,x) 为真当且仅当存在使用 k 的解决方案恰好 k 数字，从第一个 i 元素开始，总和为 x。

此解决方案的复杂度为 O(n*N*Z)，其中 n - 数组中元素的数量，N - 数量您可以使用的不同元素，Z - 目标总和。