题解 | #24点游戏算法#二维树层深度优先搜索

import itertools
nums = [int(x) for x in input().split()]
 
operation_fist_list = ["+", "-", "*", "/"]
operation_sec_list = ["-", "/"]
def cal24(candidates):
    if len(candidates)==1:
        if candidates[0]==24:
            return True
        else:
            return False
     
    for i in range(len(candidates)):
        for j in range(i+1, len(candidates)):
            for operation in operation_fist_list:
                if operation=="/" and candidates[j]==0: return False
                result = eval("{}{}{}".format(candidates[i], operation, candidates[j]))
                if cal24([result]+candidates[:i]+candidates[i+1:j]+candidates[j+1:]):
                    return True
            for operation in operation_sec_list:
                if operation=="/" and candidates[i]==0: return False
                result = eval("{}{}{}".format(candidates[j], operation, candidates[i]))
                if cal24([result]+candidates[:i]+candidates[i+1:j]+candidates[j+1:]):
                    return True
    return False
 
if cal24(nums): print("true")
else: print("false")

二维树层遍历，深度优先搜索 此前的深度优先搜索每次只取一个数字，这次需要每次取出两个数字，使用两个for循环用于模拟每次取两个数字。 运算完的结果需要重新放回candidate中，此次candidates的传入使用了隐形回溯，此前一直没有意识到