网站备案空间备案吗在线外链

问题背景

在全排列问题中，尤其是包含重复元素（如 LeetCode 47. 全排列 II）时，回溯算法的实现有两个关键设计点常引发困惑：

1. 回溯函数为何不需要 index 参数？
2. 循环遍历的起点为何是 i=0 而非 index？

本文将通过对比组合问题与排列问题的差异，结合代码示例，深入分析这两大问题。

---

一、为何回溯函数不需要 index 参数？

1. 全排列问题的核心特性

全排列要求每个元素在不同位置出现，因此必须允许元素在递归的任何层级中被重新选择，只要其未被标记为已使用。例如，数组 [1,1,2] 的合法排列 [2,1,1] 中，第二个 1 出现在第三个位置，需要回溯时能重新选择之前跳过的元素。

2. index 的作用与局限性

• 组合问题：index 用于确保元素按顺序选择，避免生成重复组合（如 [1,2] 和 [2,1] 被视为同一组合）。
• 排列问题：若使用 index 限制起始位置，将导致无法生成某些合法排列。例如，若 index=1，则无法在第一个位置选择 nums[1] 的元素，遗漏类似 [2,1,1] 的排列。

3. 正确设计：用 used[] 替代 index

通过 boolean[] used 数组标记元素是否被使用，既能避免重复选择，又能允许元素在不同位置出现：

private void backtrack(List<List<Integer>> result, List<Integer> path, int[] nums, boolean[] used) {if (path.size() == nums.length) {result.add(new ArrayList<>(path));return;}for (int i = 0; i < nums.length; i++) { // 始终从0开始遍历if (used[i]) continue;              // 通过used数组控制选择// ... 剪枝与递归逻辑}
}

---

二、为何循环从 i=0 开始而非 index？

1. 排列问题的顺序敏感性

排列问题的核心是元素顺序不同即为新排列（如 [1,2,3] 和 [2,1,3] 是两种不同的排列）。因此，每次递归都必须从头扫描数组，确保每个未被使用的元素都有机会被选中。

2. 对比组合问题的循环设计

• 组合问题：从 index 开始遍历，避免重复组合。

  // 组合问题典型写法：从index开始
  for (int i = index; i < nums.length; i++) {path.add(nums[i]);backtrack(result, path, nums, i + 1); // 下一层从i+1开始path.remove(path.size() - 1);
  }
  

• 排列问题：从 i=0 开始遍历，但通过 used[] 控制元素选择。

  // 排列问题典型写法：始终从0开始
  for (int i = 0; i < nums.length; i++) {if (used[i]) continue; // 跳过已使用的元素used[i] = true;backtrack(result, path, nums, used);used[i] = false;
  }
  

3. 关键区别总结

问题类型	遍历起点	核心目标	去重方式
组合/子集	index	避免顺序不同导致的重复组合	限制起始位置
排列	i=0	允许元素出现在任意位置	used[] 标记已使用

---

三、实例分析：nums = [1,1,2]

1. 正确遍历逻辑

1. 第一层递归：遍历所有元素，选择第一个 1（索引0），标记 used[0] = true。
2. 第二层递归：再次遍历所有元素，跳过 used[0]，选择第二个 1（索引1），标记 used[1] = true。
3. 第三层递归：选择 2，生成排列 [1,1,2]。
4. 回溯后：若尝试在第一层选择第二个 1（索引1），触发剪枝条件 i > 0 && nums[i] == nums[i-1] && !used[i-1]，跳过重复分支。

2. 错误设计的影响

若强行添加 index 参数：

// 错误写法：从index开始遍历
for (int i = index; i < nums.length; i++) {if (used[i]) continue;// ...
}

• 问题：当 index=1 时，后续递归无法选择索引0的元素，导致遗漏 [2,1,1] 等排列。

---

四、总结与最佳实践

1. 关键结论

• 无需 index 参数：排列问题需遍历所有元素，通过 used[] 数组控制元素选择。
• 循环从 i=0 开始：确保每个元素有机会出现在任意位置，结合 used[] 避免重复使用。

2. 代码模板

public List<List<Integer>> permuteUnique(int[] nums) {List<List<Integer>> result = new ArrayList<>();Arrays.sort(nums); // 排序以便剪枝backtrack(result, new ArrayList<>(), nums, new boolean[nums.length]);return result;
}private void backtrack(List<List<Integer>> result, List<Integer> path, int[] nums, boolean[] used) {if (path.size() == nums.length) {result.add(new ArrayList<>(path));return;}for (int i = 0; i < nums.length; i++) { // 始终从0开始if (used[i]) continue;if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue; // 剪枝used[i] = true;path.add(nums[i]);backtrack(result, path, nums, used);path.remove(path.size() - 1);used[i] = false;}
}

3. 适用场景扩展

• 排列问题：全排列（无重复）、全排列 II（含重复）。
• 组合问题：子集、组合总和（需使用 index 参数）。

---

通过理解全排列问题的特性与回溯设计原则，可避免常见误区，写出高效且正确的算法实现。