Road to Genius: advanced #37

Each day I solve several coding challenges and puzzles from Codr's ranked mode. The goal is to reach genius rank, along the way I explain how I solve them. You do not need any programming background to get started, and you will learn a ton of new and interesting things as you go.

function backtrack(list, tempList, nums, remain, start) {
  if (remain < 0)
    return;
  else if (remain === 0)
    return list.push([...tempList]);
  for (let i = start; i < nums.length; i++) {
    tempList.push(nums[i]);
    backtrack(list, tempList, nums, 💧 - nums[i], i);
    tempList.pop();
  }
}
function combS(arr, T) {
  const list = [];
  backtrack(list, [], arr.sort((a, b) => a - b), T, 0);
  return list;
}
let A = combS([2, 3, 4], 4);
☃️ = A.length;

// 💧 = ? (identifier)
// ☃️ = ? (identifier)
// such that A = 2 (number)

This code looks quite challenging since it's related to backtracking; fortunately we only have to fix two bugs. The last bug ☃️ is peanuts, it should be A because it has to satisfy the challenge requirement (A = 2 = A.length).

To figure out the other bug 💧 we'll have to carefully analyze the code. The function backtrack is of recursive nature, it keeps calling itself until some criteria is met, like such:

function backtrack(arg) {
  if (arg == x)
    return;
  else
    backtrack(arg+1)
}

At first glimpse we have no clue what backtrack does, but we can make educated guesses by analyzing the variable names. We see the variable remain which reminds me of divide operations (~ remainders).

The else-if-statement checks if remain == 0, if so it pushes some items into list. Then the for-loop iterates over each number from nums, and calls the backtrack function as:

for (...) {
   backtrack(..., 💧 - nums[i], ...)
}

Until now I haven't seen any division related operations, except for this subtraction. In math we can use subtractions to compute the result and remainder, here's an example:

9/2 = ?
D = 9
V = 2

O = 9-2 = 7
O = 7-2 = 5
O = 5-2 = 3
O = 3-2 = 1
O = 1-2 = -1  -->  0 reached
R = |O| = 1

There are 4 subtract operations that are >= 0:
9/2 = 4 and 1 as remainder

The backtrack function appears to be doing exactly this, but in a recursive fashion. It's taking the current remain and subtracting some number, the next recursion then checks if that result is zero. So my best bet is that 💧 should be remain.

But we want to be 100% sure of this, so let's take the challenge's input and quickly calculate if we get A=2, in pseudo-code:

backtrack(remain = 4)

-- backtrack(remain = 4-2 = 2)
---- backtrack(remain = 2-2 = 0) --> push
---- backtrack(remain = 2-3 = -1)
---- backtrack(remain = 2-4 = -2)

-- backtrack(remain = 4-3 = 1)
---- backtrack(remain = 1-3 = -2)
---- backtrack(remain = 1-4 = -3)

-- backtrack(remain = 4-4 = 0)  --> push

As you can see we have 2 push operations, both of these pushed 2 arrays into the list array inside combS. So eventually A = list.length = 2.

By solving these challenges you train yourself to be a better programmer. You'll learn newer and better ways of analyzing, debugging and improving code. As a result you'll be more productive and valuable in business. Get started and become a certified Codr today at https://nevolin.be/codr/