Interview Question - the perfect curry

README.md

We want to prepare the perfect curry with ingredients P, Q, and R. "A" is a zero-indexed array of N integers. Elements of A are integers within the range [−99,999,999 to 99,999,999] The curry is a string consisting of N characters such that each character is either P, Q, or R and the corresponding index of the array is the weight of each ingredient. The curry is perfect if the sum of the total weights of P, Q, and R is equal. Write a function function makeCurry(Array); such that, given a zero-indexed array Array consisting of N integers, returns the perfect curry of this array. The function should return the string "noLuck" if no perfect curry exists for that Array. For example, given array A such that

A[0] = 3
A[1] = 7
A[2] = 2
A[3] = 5
A[4] = 4

the function may return "PQRRP", as explained above. Given array A such that

A[0] = 3
A[1] = 6
A[2] = 9

the function should return "noLuck".

thePerfectCurry.js

// Tests if selected elements add up to target
function check(a, selection, target) {
    let sum = 0;
    for (let i = 0; i < a.length; i++) {
        if (((selection >> i) & 1) == 1)
            sum += a[i];
    }
    return sum == target;
}

// Remove the selected elements
function exclude(a, selection) {
    let res = [a.length];
    let j = 0;
    for (let i = 0; i < a.length; i++) {
        if (((selection >> i) & 1) == 0)
            res[j++] = a[i];
    }
    return res
}

function getCurry(a) {
    console.log(a)
    // Sum of all
    let sum = a.reduce((accumulator, currentValue) => accumulator + currentValue);
    if (sum % 3 > 0)
        return "noLuck";
    let target = sum / 3;
    let max1 = 1 << a.length; // 2^length
    console.log(max1);
    for (let i = 0; i < max1; i++) {
        if (check(a, i, target)) {
            let b = exclude(a, i);
            let max2 = 1 << b.length; // 2^length
            for (let j = 0; j < max2; j++) {
                if (check(b, j, target))
                    return formatSolution(i, j, a.length);
            }
        }
    }
    return "noLuck";
}

function formatSolution(p, q, len) {
    let res = new Array(len)
    res.fill('R')
    let j = 0;
    for (let i = 0; i < len; i++) {
        if (((p >> i) & 1) == 1)
            res[i] = 'P';
        else {
            if (((q >> j) & 1) == 1)
                res[i] = 'Q';
            j++;
        }
    }
    return new String(res);
}

//		let a = [3, 7, 2, 5, 4]
		let a = [1, 1, 2, -1, 5, 3, 8, -6, 4, 1]
// let a = [5, 4, 3, 3, 3, 3, 3, 3]
console.log(getCurry(a))