679. 24 Game

[Tcdian]

679. 24 Game

你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *，/，+，-，(，) 的运算得到 24。

Example 1

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

Example 2

Input: [1, 2, 1, 2]
Output: False

Note

• 除法运算符 / 表示实数除法，而不是整数除法。例如 4 / (1 - 2/3) = 12 。
• 每个运算符对两个数进行运算。特别是我们不能用 - 作为一元运算符。例如，[1, 1, 1, 1] 作为输入时，表达式 -1 - 1 - 1 - 1 是不允许的。
• 你不能将数字连接在一起。例如，输入为 [1, 2, 1, 2] 时，不能写成 12 + 12 。

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var judgePoint24 = function(nums) {
    let result = false;
    const operators = ['+', '-', '*', '/'];
    backtracking(nums);
    return result;

    function backtracking(nums) {
        if (result) {
            return;
        }
        if (nums.length === 1) {
            result = Math.abs(nums[0] - 24) < 0.0000001;
            return;
        }
        for (let i = 0; i < nums.length; i++) {
            for (let j = 0; j < nums.length; j++) {
                if (i === j) {
                    continue;
                }
                for (let s = 0; s < operators.length; s++) {
                    if (i < j) {
                        backtracking([
                            ...nums.slice(0, i),
                            ...nums.slice(i + 1, j),
                            ...nums.slice(j + 1),
                            calc(nums[i], nums[j], operators[s])
                        ]);
                    } else {
                        backtracking([
                            ...nums.slice(0, j),
                            ...nums.slice(j + 1, i),
                            ...nums.slice(i + 1),
                            calc(nums[i], nums[j], operators[s])
                        ]);
                    }
                }
            }
        }
    }
    function calc(a, b, operator) {
        switch(operator) {
            case '+':
                return a + b;
            case '-':
                return a - b;
            case '*':
                return a * b;
            case '/':
                return a / b;
        }
    }
};

• TypeScript Solution

function judgePoint24(nums: number[]): boolean {
    let result = false;
    const operators: ['+', '-', '*', '/'] = ['+', '-', '*', '/'];
    backtracking(nums);
    return result;

    function backtracking(nums: number[]) {
        if (result) {
            return;
        }
        if (nums.length === 1) {
            result = Math.abs(nums[0] - 24) < 0.0000001;
            return;
        }
        for (let i = 0; i < nums.length; i++) {
            for (let j = 0; j < nums.length; j++) {
                if (i === j) {
                    continue;
                }
                for (let s = 0; s < operators.length; s++) {
                    if (i < j) {
                        backtracking([
                            ...nums.slice(0, i),
                            ...nums.slice(i + 1, j),
                            ...nums.slice(j + 1),
                            calc(nums[i], nums[j], operators[s])
                        ]);
                    } else {
                        backtracking([
                            ...nums.slice(0, j),
                            ...nums.slice(j + 1, i),
                            ...nums.slice(i + 1),
                            calc(nums[i], nums[j], operators[s])
                        ]);
                    }
                }
            }
        }
    }
    function calc(a: number, b: number, operator: '+' | '-' | '*' | '/') {
        switch(operator) {
            case '+':
                return a + b;
            case '-':
                return a - b;
            case '*':
                return a * b;
            case '/':
                return a / b;
        }
    }
};