Mieszko

This is the solution for a difficult problem in ECS529U Algorithms and Data Structures, Lab 10. Try to understand the solution as well as you can.

Given an array, A, and a number, s, find the set of numbers in A for which the sum is the closest to s out of all sets of numbers in A.

We start with a function, closestSum. It returns an array of numbers that sum to the closest value to s (out of all the numbers in A).

function closestSum(A, s) {
    return [];
}

Base case

If the array A is empty then we are at the base case.

if(A.length === 0) return A;

Step case

Consider the first number in A.

let currentNumber = A[0];
let AWithoutCurrentNumber = A.slice(1, A.length);

Are we better off with currentNumber in our final set of numbers or without it?

// withC is an array with currentNumber and the set with the closest sum to s - currentNumber
let withC = [currentNumber, ...closestSum(AWithoutCurrentNumber, s - currentNumber)];

// withoutC is an array without currentNumber and the set with the closest sum to s
let withoutC = closestSum(AWithoutCurrentNumber, s);

let diffSumWithAndS = Math.abs(sum(withC) - s);
let diffSumWithoutAndS = Math.abs(sum(withoutC) - s);

if(diffSumWithAndS < diffSumWithoutAndS) {
    // Sum with currentNumber is closer to s
    return with;
} else {
    // Sum without currentNumber is closer to s
    return without;
}

Final code

This function has a runtime complexity of O(2n) because in every call (except the base case) the function calls itself twice. If it called itself once then the complexity would be O(n), and for three times it would be O(3n).

function closestSum(A, s) {
    if(A.length === 0) return A;

    function sum(A) {
        return A.reduce((a, b) => a + b, 0);
    }

    let currentNumber = A[0];
    let AWithoutCurrentNumber = A.slice(1, A.length);

    let withC = [currentNumber, ...closestSum(AWithoutCurrentNumber, s - currentNumber)];
    let withoutC = closestSum(AWithoutCurrentNumber, s);

    let diffSumWithAndS = Math.abs(sum(withC) - s);
    let diffSumWithoutAndS = Math.abs(sum(withoutC) - s);

    if(diffSumWithAndS < diffSumWithoutAndS) {
        // Sum with currentNumber is closer to s
        return withC;
    } else {
        // Sum without currentNumber is closer to s
        return withoutC;
    }
}

This is one of the hardest exercises in ECS529U Algorithms and Data Structures at QMUL. If you are studying this module then make sure that you understand this algorithm.