Road to Genius: advanced #37
Tags: javascript, beginners, codenewbie, computerscience
Published: 2020-07-02 17:17:51

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.

```JS
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:

```JS
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:
```JS
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:

```JS
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:
```JS
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`.

![coding challenge answer](https://dev-to-uploads.s3.amazonaws.com/i/gaged6f5uv6vv6raarrp.png)

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/