Find the closest sum to s

Context

This is the solution for a difficult problem in ECS529U Algorithms and Data Structures (Queen Mary University of London), Lab 10. Try to understand the solution as well as you can.

Note: I will use the term "list" but since I am using JavaScript, it is actually an array.

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

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

// {A} is a list of numbers
// {s} is a number
function closestSum(A, s) {
  // return some of the numbers in {A}
  // We want the combination of numbers that summed together, are closest to {s}
  // out of all the combinations of numbers in {A}
  return [];
}

Recursion

This solution uses recursion. Recursion is a way of solving problems by breaking them down into smaller problems. The function closestSum calls itself to solve the smaller problems.

Base case

If the list A is empty then we are at the base case. Since this function will call itself, eventually it has to stop calling itself. The base case is what we call that stopping point.

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

If you get an error such as "Maximum call stack size exceeded", then probably something is wrong with your base case and it is not stopping the function from calling itself. It could also be that your input is too big for the function to handle.

Step case

Pick a number from A and figure out if we're better off with this number in the final list, or without it.

// Each time {closestSum} is called, we take one number from {A}
// It doesn't matter which number we take, so just take the first one
const currentNumber = A[0];
const withoutCurrentNumber = A.slice(1, A.length);

The next line is complex. We need to figure out if we're better off with currentNumber in the final list, or without it.

To do this, we call closestSum again but tell it that currentNumber does not exist (so the sum we're looking for is s - currentNumber). This is how we get one step closer to the base case.

// {withC} is the final list of numbers- with {currentNumber} definitely in it
// Because we use recursion, every number in {A} will be checked
const withC = [currentNumber, ...closestSum(withoutCurrentNumber, s - currentNumber)];

// {withoutC} is the final list of numbers- as if {currentNumber} did not exist
const withoutC = closestSum(withoutCurrentNumber, s);

Now, which list has a sum closer to s? Is it withC or withoutC?

// For both lists, work out the difference between the sum and {s}
// Lower is better because it is closer to {s}
// Math.abs() is used to make sure the difference is positive ({A} can have negative numbers)
const differenceWithC = Math.abs(sum(withC) - s);
const differenceWithoutC = Math.abs(sum(withoutC) - s);

if(differenceWithC < differenceWithoutC) {
  // {withC} is better (lower difference between it and {s}), so use {withC}
  // Sum with currentNumber is closer to s
  return with;
} else {
  // {withoutC} is better (lower difference between it and {s}), so use {withoutC}
  // Sum without currentNumber is closer to s
  return without;
}

Runtime complexity (Big O Notation)

This algorithm has a runtime complexity of O(2n) because in every call (except the base case) the function calls itself twice.

Size of A Actual recursive calls
1 2
2 6
3 14
4 30
10 2046
20 2097150

The number of recursive calls is roughly 2n (where n is the length of A). We can see that the number of calls roughly doubles when the length of A increases by 1.

If the funtion called itself once then the complexity would be O(n), and for three times it would be O(3n).

Final code

⚠️ The code below has two issues to prevent copy/pasting without understanding. See if you can explain the code line by line. Good luck!

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

  const currentNumber = A[0];
  const withoutCurrentNumber = A.slice(1, A.length);

  const withC = [currentNumber, ...closestSum(withoutCurrentNumber, s - currentNumber)];
  const withoutC = closestSum(withoutCurrentNumber, s);

  const differenceWithC = Math.abs(sum(withC) - s);
  const differenceWithoutC = Math.abs(sum(withoutC) - s);

  if (differenceWithC > differenceWithoutC) {
    // 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, make sure that you understand this algorithm.

More

Find the closest sum to s
This is the solution for a difficult problem in ECS529U Algorithms and Data Structures (Queen Mary University of London), Lab 10. Try to…
Building safe atomic transactions with Deno KV
The Deno Team are building a unique product. It's an all-javascript development experience with _very_ simple deployments: Deno KV is a…
Social media image previews with Deno Fresh
When you share a link on Twitter, Facebook, LinkedIn or Discord, you can see an image with a preview of the page you're linking to. This…
See more articles
Email