Array Edition (Recursion, Algorithm)

Have the function ArrayAddition(arr) take the array of numbers stored in arr and return the string true if any combination of numbers in the array (excluding the largest number) can be added up to equal the largest number in the array, otherwise return the string false. For example: if arr contains [4, 6, 23, 10, 1, 3] the output should return true because 4 + 6 + 10 + 3 = 23. The array will not be empty, will not contain all the same elements, and may contain negative numbers.

Input: [5,7,16,1,2] -> Output: false
Input: [3,5,-1,8,12] -> Output: true  

Solution

function ArrayAddition(arr) {
  const largest = Math.max(...arr);
  const newArr = arr.filter((num, idx) => idx !== arr.indexOf(largest));
  
  const n = newArr.length;
  
  // Check 2^n possible outcomes (bit mask)
  for (let mask = 1; mask < (1 << n); mask++) {
    let sum = 0;
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) {
        sum += newArr[i];
      }
    }
    if (sum === largest) {
      return "true";
    }
  }
  
  return "false";
}

console.log(ArrayAddition([4, 6, 23, 10, 1, 3])); // "true"

Prerequisite - Understanding << (Bit Shift)

The << operator shifts the bits of a number to the left.

For example, 1 << i moves the bit 1 to the left by i positions, which is the same as calculating 2 raised to the power of i.

First, let's look at 1 in binary:

1 (decimal) = 00001 (binary, shown with 5 digits)

What the << operator does

The << operator shifts all bits to the left and fills the empty spots on the right with 0.

1 << 0   →  shift 00001 by 0   →  00001  (decimal 1)
1 << 1   →  shift 00001 by 1   →  00010  (decimal 2)
1 << 2   →  shift 00001 by 2   →  00100  (decimal 4)
1 << 3   →  shift 00001 by 3   →  01000  (decimal 8)
1 << 4   →  shift 00001 by 4   →  10000  (decimal 16)

In this case,

mask & (1 << i)

This meaning:

• Let’s make i position 1, and 0 for the rest.
• So, it becomes mask & (the number) → Highlight only the i-th position and check whether the i-th position of mask is 1 or not.

For example,

When i = 2, 1 << 2 = 00100. This acts like a flashlight that only lights up position 2.

mask       = 00101   (mask=5)
1 << 2     = 00100   (flashlight lighting up only position 2)
-----------  AND operation (only positions where both are 1 stay 1)
result     = 00100   → not 0, so we confirm "position 2 was 1!"

mask       = 00101   (mask=5)
1 << 1     = 00010   (flashlight lighting up only position 1)
-----------  AND
result     = 00000   → 0, so we confirm "position 1 was 0"

Explanation - mask < (1 << n)

for (let mask = 1; mask < (1 << n); mask++) {

mask < (1 << n) is the part that decides when the loop should stop; in other words, the termination condition of the loop.

Example

When n=3, 1 << n becomes 8.

The number of subsets you can make from 3 elements is exactly 2³, which equals 8.

Let’s say we pass [4, 6, 10] as the argument, and we get,

Should we include 4? → 2 choices (include it / do not include it)
Should we include 6? → 2 choices (include it / do not include it)
Should we include 10? → 2 choices (include it / do not include it)

Therefore, the condition now becomes:

for (let mask = 1; mask < 8; mask++) {

This means,

1. Start mask at 1, and keep looping as long as mask is less than 8.
2. Since the condition is mask < 8, mask actually goes through 1, 2, 3, 4, 5, 6, 7.
3. The moment mask becomes 8, the condition turns false (8 < 8 is false), so the loop stops.

Let's check this in a table (n=3, newArr=[4,6,10])

The loop runs exactly 7 times, from 1 to 7. This corresponds to all 8 possible subsets when n=3 (000 through 111), minus the empty subset (mask=0, meaning nothing is selected).

Explanation - Bit Mask

What is bit mask?

A bit mask is a way to use the individual bits of a number to represent multiple on or off values at once. Instead of using several variables, you can pack many flags into one number.

Case Scenario

In the case of Array Edition, we use it to represent every possible subset of the array. Each bit in the mask corresponds to one element.

• If the bit is 1, that element is included in the subset.
• If it is 0, the element is excluded

For an array of length n, there are 2^n possible subsets. By looping mask from 1 to (1 << n) - 1, we can check every subset exactly once. For each mask, we look at each bit position i. If the i-th bit is set, we add newArr[i] to the sum.

This lets us test whether any combination of the remaining numbers can add up to the largest number, without writing separate loops for every possible group size.

Now, let’s review the code line by line.

const largest = Math.max(...arr);

• Get the largest number from the array.

const newArr = arr.filter((num,idx)=> idx !== arr.indexOf(largest));

• Make a new array including only numbers that are not the largest.

const n = newArr.length;

• Get the length

for (let mask = 1; mask < (1 << n); mask++) {
    let sum = 0;
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) {
        sum += newArr[i];
      }
    }
    if (sum === largest) {
      return "true";
    }
  }

Setup

newArr = [4, 6, 10]
index:     0  1  2
largest = 16

When mask=1 (Outer Loop 1)

let sum = 0; // Reset sum

Inner loop runs through checking i = 0, 1, 2

i=0:  mask & (1<<0) = 001 & 001 = 001 (true) → sum += newArr[0] → sum = 0+4 = 4
i=1:  mask & (1<<1) = 001 & 010 = 000 (false) → not added
i=2:  mask & (1<<2) = 001 & 100 = 000 (false) → not added

mask = 2

let sum = 0;

i=0:  010 & 001 = 000 (false) → not added
i=1:  010 & 010 = 010 (true) → sum += newArr[1] → sum = 0+6 = 6
i=2:  010 & 100 = 000 (false) → not added

→ sum = 6. 6 === 16? No → move to next mask.

mask = 3

let sum = 0;

i=0:  011 & 001 = 001 (true) → sum += newArr[0] → sum = 0+4 = 4
i=1:  011 & 010 = 010 (true) → sum += newArr[1] → sum = 4+6 = 10
i=2:  011 & 100 = 000 (false) → not added

→ sum = 10. Is 10 === 16? No → move to next mask.

mask = 4

let sum = 0;

i=0:  100 & 001 = 000 (false) → not added
i=1:  100 & 010 = 000 (false) → not added
i=2:  100 & 100 = 100 (true) → sum += newArr[2] → sum = 0+10 = 10

→ sum = 10. Is 10 === 16? No → move to next mask.

mask = 5

let sum = 0;

i=0:  101 & 001 = 001 (true) → sum += newArr[0] → sum = 0+4 = 4
i=1:  101 & 010 = 000 (false) → not added
i=2:  101 & 100 = 100 (true) → sum += newArr[2] → sum = 4+10 = 14

→ sum = 14. Is 14 === 16? No → move to next mask.

mask = 6 ★ this is where we find the answer!

let sum = 0;

i=0:  110 & 001 = 000 (false) → not added
i=1:  110 & 010 = 010 (true) → sum += newArr[1] → sum = 0+6 = 6
i=2:  110 & 100 = 100 (true) → sum += newArr[2] → sum = 6+10 = 16

→ sum = 16. Is 16 === 16? Yes! → return "true" runs → the function ends immediately!

The loop stops here

Since we already found the answer at mask=6, mask=7 never runs at all. The moment the function hits a return statement, the entire function ends.

Each time mask increases by 1, a different subset gets built. The sum of that subset gets calculated and compared against largest.

The moment they match, the function returns the answer right away and stops. If it had gone all the way through (up to mask=7) without finding a match, the loop would have ended and return "false" would have run instead.

Pseudo

1. Find the largest number in the array (largest)
2. Create a newArray excluding largest
3. Get the length of newArray (n)
4. Calculate the number of possible combinations (2 to the power of n)
5. Create a loop over all possible combinations - Outer Loop (mask from 1 to 2^n - 1)
   5-1. Initialize sum to 0 - reset every time the outer loop runs
6. Create a loop over the length of newArray - Inner Loop (i from 0 to n-1)
7. Calculate the bitwise AND of mask (outer loop) and (1<<i) (inner loop)
8. If the AND result is truthy (non-zero), add the corresponding newArray[i] value to sum
9. After the inner loop finishes, check if sum equals largest
   → if they match, return true
10. If no match is found after the outer loop finishes, return false