题解 | #24点游戏算法#

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    // Write your code here
    while(line = await readline()){
        let res =  false;
        let nums = line.split(' ');
        let used = new Set(); // 用于记录回溯
        let opers = ['+', '-', '*', '/'];
        backtrack(0, '');
        // 回溯法，用深度遍历，把所有情况都遍历一次，找到24就直接返回
        function backtrack(index, str) {
            if (res) return; // 找到结果，结束遍历
            if (index === 4 && eval(str) === 24) { // 4个数字都用完且结果等于24 则直接返回
                res = true;
                return;
            }
            for (let i = 0; i < 4; i++) {
                if (!used.has(i)) {
                    used.add(i);
                    for (let j = 0; j < 4; j++) {
                        // 不考虑括号的情况
                        backtrack(i + 1, str === '' ? nums[i] : `${str} ${opers[j]} ${nums[i]}`);
                        // 遇到加减运算符的话要把有括号的情况也考虑进去
                        if (str[str.length - 1] !== ')' && j < 2) {
                            backtrack(i + 1, str.replace(/(\d+)$/, `($1 ${opers[j]} ${nums[i]})`));
                        }
                    }
                    used.delete(i);
                }
            }
        }
        console.log(res);
    }
}()