调试递归全排列代码时遇索引越界错误，求问题解析

问题背景 #

LeetCode全排列问题要求给定数组返回其所有可能的排列，例如输入[1,2,3]，需输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]。你编写的递归回溯代码出现List Index Out of Range索引越界错误，且仅能生成第一个排列，以下针对这类常见错误的原因及修正逻辑进行分析：

原代码错误原因 #

1. 索引越界的直接诱因 #

• 非法索引访问：若代码中用当前路径的长度作为数组索引（如nums[len(path)]），当路径长度等于数组长度时（递归终止前的临界状态），会访问超出数组范围的索引（数组最大索引为len(nums)-1），直接触发越界错误。
• 回溯时索引操作错误：如果在插入元素后，使用了错误的索引执行pop操作（比如固定索引而非对应插入位置），当路径长度变化后，该索引不再合法，也会导致越界。

2. 仅生成第一个排列的核心问题 #

• 未正确回溯状态：递归调用后未恢复当前路径的状态（比如遗漏pop操作，或pop位置错误），导致递归深入后无法回到上一层分支，无法遍历其他排列的可能性。
• 未标记已使用元素：循环遍历数组时未跳过已加入当前路径的元素，逻辑上只能按顺序生成第一个排列，无法切换起始元素或选择其他未使用的元素。
• 结果引用错误：直接将路径列表的引用添加到结果中，后续对路径的修改会覆盖已存入结果的内容，最终仅能看到第一个排列的残留（或被覆盖后的错误结果）。

修正逻辑 #

1. 解决索引越界 #

• 严格限制数组索引范围：遍历数组时使用range(len(nums))，通过布尔数组标记已使用元素，而非依赖路径长度获取元素。
• 回溯操作匹配：若使用append添加元素，对应使用pop()（默认弹出最后一个元素）恢复状态；若使用insert插入到指定位置，必须pop对应索引的元素，确保索引始终合法。

2. 生成所有排列的关键修正 #

• 强制状态回溯：递归调用后必须执行状态恢复操作，确保路径回到调用前的状态，示例代码片段：

  path.append(nums[i])
  backtrack(path, used)
  path.pop()  # 递归返回后弹出元素，回到上一层状态
  

• 标记已使用元素：使用与数组长度一致的布尔数组used，元素加入路径时标记为True，回溯时重置为False，避免重复使用：

  used[i] = True
  path.append(nums[i])
  backtrack(path, used)
  used[i] = False
  

• 添加结果副本：将当前路径的副本存入结果，而非直接添加引用，避免后续修改覆盖已有结果：

  if len(path) == len(nums):
      res.append(path.copy())  # 或 res.append(list(path))
      return
  

修正后的完整示例代码 #

def permute(nums):
    res = []
    n = len(nums)
    used = [False] * n
    
    def backtrack(path):
        if len(path) == n:
            res.append(path.copy())
            return
        for i in range(n):
            if not used[i]:
                used[i] = True
                path.append(nums[i])
                backtrack(path)
                # 回溯恢复状态
                path.pop()
                used[i] = False
    
    backtrack([])
    return res

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