679. 24 Game

Problem

You are given an integer array cards of length 4. You have four cards, each containing a number in the range [1, 9]. You should arrange the numbers on these cards in a mathematical expression using the operators ['+', '-', '*', '/'] and the parentheses '(' and ')' to get the value 24.

You are restricted with the following rules:

The division operator '/' represents real division, not integer division.

• For example, 4 / (1 - 2 / 3) = 4 / (1 / 3) = 12.

  Every operation done is between two numbers. In particular, we cannot use '-' as a unary operator.

• For example, if cards = [1, 1, 1, 1], the expression "-1 - 1 - 1 - 1" is not allowed.

  You cannot concatenate numbers together

• For example, if cards = [1, 2, 1, 2], the expression "12 + 12" is not valid.

Return true if you can get such expression that evaluates to 24, and false otherwise.

  Example 1:

Input: cards = [4,1,8,7]
Output: true
Explanation: (8-4) * (7-1) = 24

Example 2:

Input: cards = [1,2,1,2]
Output: false

  Constraints:

• cards.length == 4

• 1 <= cards[i] <= 9

Solution

/**
 * @param {number[]} cards
 * @return {boolean}
 */
var judgePoint24 = function(cards) {
  const isValid = x => Math.abs(x - 24) < 0.0000001
  const aux = (arr = []) => {
    if (arr.length === 1) {
      return isValid(arr[0])
    }
    let valid = false
    for (let i = 0; i < arr.length; i++) {
      for (let j = i + 1; j < arr.length; j++) {
        const nextArr = arr.filter((x, index) => index !== i && index !== j)
        valid = valid || aux([...nextArr, arr[i] + arr[j]])
          || aux([...nextArr, arr[i] - arr[j]])
          || aux([...nextArr, arr[j] - arr[i]])
          || aux([...nextArr, arr[i] * arr[j]])
          || aux([...nextArr, arr[i] / arr[j]])
          || aux([...nextArr, arr[j] / arr[i]])
      }
    }
    return valid
  }

  return aux(cards)
};

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).