leetcode46.全排列：回溯算法中元素利用的核心逻辑

一、题目深度解析与排列特性

题目描述

给定一个不含重复数字的数组nums，返回其所有可能的全排列。解集不能包含重复的排列，且排列可以按任意顺序返回。例如：

• 输入：nums = [1,2,3]
• 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

核心特性分析

1. 排列定义：每个元素必须且仅使用一次，顺序不同视为不同排列
2. 元素独立性：数组不含重复元素，无需考虑去重处理
3. 排列总数：n个元素的全排列数目为n!

二、回溯解法的核心实现与元素利用逻辑

完整回溯代码实现

class Solution {
    List<Integer> temp = new LinkedList<>();  // 存储当前排列
    List<List<Integer>> res = new ArrayList<>();  // 存储所有排列

    public List<List<Integer>> permute(int[] nums) {
        backtracking(nums);  // 开始回溯
        return res;
    }

    public void backtracking(int[] nums) {
        if (temp.size() == nums.length) {  // 终止条件：当前排列长度等于数组长度
            res.add(new ArrayList<>(temp));  // 收集当前排列
            return;
        }

        for (int i = 0; i < nums.length; i++) {  // 遍历所有元素
            if (temp.contains(nums[i])) {  // 剪枝条件：当前元素已在排列中
                continue;
            }

            temp.add(nums[i]);  // 选择当前元素
            backtracking(nums);  // 递归处理剩余元素
            temp.removeLast();  // 回溯：撤销选择
        }
    }
}

核心设计解析

1. 元素利用方式：

   for (int i = 0; i < nums.length; i++)
   

   • 每次递归从头遍历所有元素，确保每个元素都有机会被选中
   • 通过temp.contains(nums[i])判断元素是否已被使用，避免重复使用

2. 终止条件：

   if (temp.size() == nums.length)
   

   • 当临时列表长度等于数组长度时，说明已生成一个完整排列
   • 此时收集结果并返回

3. 状态回退：

   temp.removeLast();
   

   • 递归返回后，撤销当前选择，恢复状态，以便尝试其他可能性

三、元素利用的核心逻辑与递归流程

1. 如何确保每个元素仅被使用一次？

关键机制：

• 动态检查：在每次选择元素时，检查该元素是否已在临时列表中
• 回溯恢复：递归返回后，撤销选择，使元素可被后续路径使用

示例说明：

• 处理[1,2,3]时：
  • 路径1→2→3：选择1后，递归时跳过1，选择2；再递归时跳过1和2，选择3
  • 路径1→3→2：选择1后，递归时跳过1，选择3；再递归时跳过1和3，选择2
  • 每个元素在当前路径中仅被使用一次，但在不同路径中可被重复选择

2. 递归调用树与元素选择

backtracking([1,2,3])
├─ temp=[]
│  ├─ 选择1 → temp=[1]
│  │  ├─ 选择2 → temp=[1,2]
│  │  │  └─ 选择3 → temp=[1,2,3] → 收集[1,2,3]
│  │  └─ 选择3 → temp=[1,3]
│  │     └─ 选择2 → temp=[1,3,2] → 收集[1,3,2]
│  ├─ 选择2 → temp=[2]
│  │  ├─ 选择1 → temp=[2,1]
│  │  │  └─ 选择3 → temp=[2,1,3] → 收集[2,1,3]
│  │  └─ 选择3 → temp=[2,3]
│  │     └─ 选择1 → temp=[2,3,1] → 收集[2,3,1]
│  └─ 选择3 → temp=[3]
│     ├─ 选择1 → temp=[3,1]
│     │  └─ 选择2 → temp=[3,1,2] → 收集[3,1,2]
│     └─ 选择2 → temp=[3,2]
│        └─ 选择1 → temp=[3,2,1] → 收集[3,2,1]

• 每个节点表示当前路径的选择状态
• 每个元素在每层递归中都有机会被选中，只要它尚未被当前路径使用

四、递归流程深度模拟：以输入[1,2,3]为例

关键递归路径：

1. 初始状态：

   • temp = []
   • 循环遍历i=0（元素1），选择1，递归

2. 选择1后：

   • temp = [1]
   • 循环遍历i=0（元素1），已在temp中，跳过
   • 循环遍历i=1（元素2），选择2，递归

3. 选择2后：

   • temp = [1,2]
   • 循环遍历i=0（元素1）和i=1（元素2），均已在temp中，跳过
   • 循环遍历i=2（元素3），选择3，递归

4. 选择3后：

   • temp = [1,2,3]
   • 满足终止条件，收集[1,2,3]
   • 回溯，撤销选择3，temp=[1,2]

5. 继续回溯：

   • 撤销选择2，temp=[1]
   • 选择3，temp=[1,3]
   • 递归处理剩余元素…

6. 最终结果：

   [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
   

五、算法复杂度分析

1. 时间复杂度

• O(n × n!)：
  • 排列总数为n!
  • 每个排列需O(n)时间复制到结果集

2. 空间复杂度

• O(n)：
  • 递归栈深度最大为n
  • temp列表长度最多为n
  • 结果集空间O(n × n!)

六、核心技术点总结：全排列的元素利用策略

1. 全局遍历策略

• 从头开始遍历：每次递归都从数组第一个元素开始检查
• 动态过滤：通过temp.contains()动态过滤已使用元素

2. 回溯状态控制

• 选择与撤销：选择元素后递归，返回后撤销选择
• 状态一致性：确保每次递归时临时列表状态正确

3. 终止条件设置

• 长度判断：当临时列表长度等于数组长度时终止
• 结果收集：及时收集完整排列

七、常见误区与优化建议

1. 未使用动态检查

• 错误做法：通过固定索引位置选择元素

  for (int i = start; i < nums.length; i++) // 错误，无法生成所有排列
  

• 正确逻辑：每次递归从头遍历所有元素，动态过滤已使用元素

2. 未复制列表直接添加

• 错误做法：

  res.add(temp); // 错误：所有排列指向同一引用
  

• 正确做法：

  res.add(new ArrayList<>(temp)); // 复制列表内容
  

3. 优化建议：使用布尔数组标记已使用元素

boolean[] used = new boolean[nums.length]; // 标记元素是否已使用

public void backtracking(int[] nums) {
    if (temp.size() == nums.length) {
        res.add(new ArrayList<>(temp));
        return;
    }
    
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue; // 已使用元素跳过
        
        used[i] = true; // 标记已使用
        temp.add(nums[i]);
        backtracking(nums);
        temp.removeLast();
        used[i] = false; // 撤销标记
    }
}

• 优势：contains()方法时间复杂度O(n)，布尔数组判断仅需O(1)
• 适用场景：数组长度较大时性能提升明显

八、总结：回溯算法中元素利用的通用模式

本算法通过回溯法系统枚举所有可能的排列，核心在于：

1. 全局遍历策略：每次递归从头遍历所有元素，动态过滤已使用元素
2. 状态回退机制：递归返回后撤销选择，确保元素可被后续路径使用
3. 终止条件控制：当收集到完整排列时终止递归，避免无效搜索

理解这种解法的关键是把握递归过程中状态的变化路径，以及如何在每个节点动态选择未使用元素。这种元素利用策略不仅适用于全排列问题，还可扩展到组合、子集等问题的变种，是回溯算法的核心技术之一。