题解 | #24点游戏算法#

def fun(nums, op):
    if op == "+":
        return sum(nums)
    elif op == "-":
        return nums[0]-nums[1]
    elif op == "*":
        return nums[0]*nums[1]
    else:
        return nums[0]/nums[1]

def dfs(an, nums, op,visited,length, n,flag):
    if length>=2:
        # print(nums,op)
        nums[0] = fun(nums,op)
        if nums[0] ==24:
            # print(visited,nums,op)
            flag[0] = True
            # print(flag)
            return 0
        if length==n and nums[0]!=24:
            return 0
    for i in range(n):
        if visited[i]:
            pass
        else:
            temp0,temp1 = nums[0],nums[1]
            visited[i] = True
            nums[1] = an[i]
            for opi in ["+","-","*","/"]:
                # print(nums)
                dfsret = dfs(an, nums, opi, visited,length+1, n,flag)
                if flag[0]:
                    break
                #回溯
                nums[0] = temp0
                # print(nums)
            #回溯
            nums[0],nums[1] = temp0,temp1
            visited[i] = False

if __name__ == "__main__":
    an = list(map(int, input().split()))
    n = len(an)
    nums = [-1,0]
    op = "+"
    visited = [False] * n
    flag = [False]
    for i in range(n):
        nums[0] = an[i]
        visited[i] = True
        dfsret = dfs(an, nums, op, visited,1, n,flag)
        # print(flag)
        if flag[0]:
            break
        visited[i] = False
    if flag[0]:
        print("true")
    else:
        print("false")

深度优先递归遍历数组。

状态变量：visited（访问状态，初始值全false）、nums（计算结果，新遍历元素，初始值无要求）、op(运算操作，，初始值无要求)、flag=[false]（用于判断是否有满足24点的情况，初始值为false）

每次计算结果ret保存在nums[0]中，新遍历的元素保存在nums[1]中。这样做是为了缩短计算时间。比用一个遍历数组和运算操作数组更快，更省空间。

递归遍历过程：首先分别以an[0]、an[1]、an[2]、an[3]为根节点，此时遍历长度为length=1，依次遍历剩余的数字。当遍历的长度length>=2时，每遍历一个元素则添加一种运算操作（+-*/四种），并计算运算结果fun（nums，op）。

递归过程中，visited、nums变量需要回溯。

递归终止条件：因为可能中途就找到满足24点的情况，需要设置终止递归的条件为：ret==24，并令flag[0]=True。

最后，通过状态变量flag判断，是否存在满足24点的情况。