Find a subset of a list of given size that sums to target value

Question

I entered a coding test where one of the questions was this: given an array A of integers of any length, and then two numbers N and Z, say whether there are Z (distinct) numbers in A such as their sum is N.

So for example (in the format A N Z):

for [1,2,3] 5 2 the answer is YES because 2+3=5
for [1,2,3] 6 2 the answer is NO because there are no two numbers in A that can be added to make 6

My solution (below) first enumerates every (unordered) combination of Z numbers in A, then sums it, and then searches for N in the list of sums.

Although this solution works fine (passed all test cases, with no timeout), I was told the score was too low for me to continue in the test.

So the question is, what can be improved?

An obvious optimization would be to calculate the sum of each combination immediately, and then stop when a match with N is found; but since I didn't run into time issues I don't think this is the problem. What is the better, more elegant/efficient solution?

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;
    }

Correct me if necessary, but it seems the number of possible comparison-combinations would be L^Z - LZ + L, where L is A.length. This is because Z determines the number of times you'll take each value in A and compare it to each of the other values -- minus each time you come across the current value in either of the subsequent combinations based on L. In other words, for [1,2,3] N 3, you'll only be comparing i=0, j=1, and k=2 -- as iterating i any further would be redundant due the requirement of discrete combinations. Also, note that Z=0 and Z>A.length are a "NO". — Cody

amit amit · Accepted Answer · 2016-01-15T08:30:42

This is a variation of the subset sum problem, which can be solved with Dynamic Programming for more efficient solution.

The main difference here, is you have an extra restriction - the number of elements that must be used. This extra restriction can be handled by adding another variable (dimension) - the number of already used elements.

The recursive formulas (which you will build the DP solution from) should be:

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])

In the above, D(i,k,x) is true if and only if there is a solution that uses k exactly k numbers, from the first i elements, and sums to x.

Complexity of this solution is O(n*N*Z) where n - number of elements in the array, N - number of distinct elements you can use, Z - target sum.

Find a subset of a list of given size that sums to target value

1 Answers