关于Java递归回溯示例的疑问：数组索引路径查找问题

我当初刚学递归回溯的时候也卡过这类问题，咱们一步步拆解开来就清楚了。先把问题再明确一遍：给定一个整数数组（比如[2,3,1,4,0]），从索引0出发，每次可以根据当前索引的值向左或向右移动对应步数（比如在索引0，值是2，就能左移2步到-2（不合法，跳过）或者右移2步到索引2），需要找出所有能到达最后一个索引的完整路径并打印。

核心思路：递归+回溯的本质 #

递归回溯其实就是“尝试所有可能，走不通就回头”的过程，对应到这个问题上：

• 我们需要记录当前走的路径，以及已经访问过的索引（防止绕圈死循环）
• 每到一个索引，先判断是不是终点：如果是，就把当前路径存下来；如果不是，就尝试左移和右移两个方向，合法的话就继续往下走，走不通就回溯（撤销当前选择，回到上一步）

结合示例一步步走（数组[2,3,1,4,0]） #

数组长度是5，最后一个索引是4，我们从索引0开始：

1. 初始状态：路径[0]，已访问索引{0}
   • 左移：0-2=-2，索引越界，跳过
   • 右移：0+2=2，索引合法且未访问，路径更新为[0,2]，已访问{0,2}
2. 现在到了索引2（值为1）：
   • 左移：2-1=1，合法未访问，路径更新为[0,2,1]，已访问{0,2,1}
     • 到了索引1（值为3）：
       • 左移：1-3=-2，越界，跳过
       • 右移：1+3=4，刚好是终点！这条路径[0,2,1,4]是有效路径，存入结果
       • 回溯：移除路径里的4，取消标记索引4，回到索引1；再移除1，取消标记1，回到索引2
   • 右移：2+1=3，合法未访问，路径更新为[0,2,3]，已访问{0,2,3}
     • 到了索引3（值为4）：
       • 左移：3-4=-1，越界
       • 右移：3+4=7，超过最大索引4，越界
     • 这条路径走不通，回溯：移除3，取消标记3，回到索引2
3. 回溯：移除2，取消标记2，回到索引0，所有可能尝试完毕

最终找到的有效路径只有[0,2,1,4]

Java代码实现及关键细节 #

下面是完整的代码，我会标注核心点：

import java.util.ArrayList;
import java.util.List;

public class JumpPathFinder {
    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 4, 0};
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> currentPath = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];
        
        // 初始化：从索引0出发
        currentPath.add(0);
        visited[0] = true;
        findPaths(nums, 0, currentPath, visited, result);
        
        // 打印所有有效路径
        System.out.println("所有到达最后索引的路径：");
        for (List<Integer> path : result) {
            System.out.println(path);
        }
    }
    
    private static void findPaths(int[] nums, int currentIndex, List<Integer> currentPath, boolean[] visited, List<List<Integer>> result) {
        int n = nums.length;
        // 递归终止条件：到达最后一个索引
        if (currentIndex == n - 1) {
            // 必须新建一个列表存入结果！因为currentPath会被回溯修改
            result.add(new ArrayList<>(currentPath));
            return;
        }
        
        int step = nums[currentIndex];
        // 尝试左移
        int leftIndex = currentIndex - step;
        if (leftIndex >= 0 && !visited[leftIndex]) {
            visited[leftIndex] = true;
            currentPath.add(leftIndex);
            // 递归进入下一层
            findPaths(nums, leftIndex, currentPath, visited, result);
            // 回溯：撤销当前选择
            currentPath.remove(currentPath.size() - 1);
            visited[leftIndex] = false;
        }
        
        // 尝试右移
        int rightIndex = currentIndex + step;
        if (rightIndex < n && !visited[rightIndex]) {
            visited[rightIndex] = true;
            currentPath.add(rightIndex);
            findPaths(nums, rightIndex, currentPath, visited, result);
            // 回溯
            currentPath.remove(currentPath.size() - 1);
            visited[rightIndex] = false;
        }
    }
}

关键细节解释 #

• visited数组：必须用它标记已访问的索引，否则会陷入无限循环（比如数组[2,0,2]，0→2→0→2...永远停不下来）
• 回溯操作：每次递归返回后，一定要把当前加入的索引从路径中移除，同时把visited标记为false——这样才能回到上一步，尝试另一个方向的可能性
• 终止条件的列表复制：不能直接把currentPath加入结果，因为currentPath是同一个对象，回溯时会被修改，所以必须用new ArrayList<>(currentPath)复制一份再存入结果

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