跳跃游戏递归求解：找到可行路径后如何立即终止递归返回结果

给定整数数组nums，初始位置为数组第一个索引，数组中每个元素的值代表当前位置可跳跃的最大长度，若能到达数组最后一个索引返回true，否则返回false。

修改给出的回溯递归代码，实现找到可行路径后立即返回结果，不需要继续执行所有已发起的冗余递归调用。

原始待修改代码 #

def canJump(self, nums: List[int]) -> bool:
    solve = [False]
    def backtrack(i):
        if solve[0] == True:
            return
        
        if i == len(nums)-1:
            solve[0] = True
            return
        
        if i >= len(nums) or nums[i] == 0:
            return
        
        for x in range(1, nums[i]+1):
            backtrack(i+x)
    
    backtrack(0)
    return solve[0]

原代码的问题在于：虽然用外部变量solve标记是否找到终点，但递归调用没有返回值，for循环中即使某一个跳跃分支已经找到可行路径，剩余的步长分支依然会依次触发递归，没法第一时间终止所有冗余调用。
直接将回溯函数改为返回布尔值的形式，就能实现找到路径后立刻逐层返回、剪枝所有后续无效调用，核心逻辑调整点如下：

• 递归到终点位置时，直接返回True表示找到可行路径
• 出现索引越界、当前位置可跳跃长度为0的情况时，返回False表示当前分支走不通
• 遍历当前位置所有可跳跃步长时，只要某一个步长的递归调用返回True，立刻向上返回True，不再遍历剩余步长
• 所有可跳跃步长都尝试完毕仍未到达终点，返回False

修改后代码 #

from typing import List

def canJump(self, nums: List[int]) -> bool:
    def backtrack(i: int) -> bool:
        # 到达数组最后一个索引，找到可行路径
        if i == len(nums) - 1:
            return True
        # 索引越界或当前位置无法继续跳跃，当前分支不通
        if i >= len(nums) or nums[i] == 0:
            return False
        # 遍历所有可跳跃的长度
        for step in range(1, nums[i] + 1):
            # 只要任意子路径能到达终点，立刻返回True终止后续递归
            if backtrack(i + step):
                return True
        # 所有跳跃长度都尝试后仍无法到达终点
        return False
    
    return backtrack(0)

注：纯回溯写法在数组长度较大、元素值较大时会出现超时问题，实际解题可以搭配记忆化搜索或者贪心算法优化时间复杂度，但上述修改已经完全满足「找到可行路径后立即返回、终止冗余递归」的要求。

内容的提问来源于stack exchange，提问作者Michael Xia