这是一个典型全排序问题，之前在力扣已经写过这种类型的题目，但是由于长时间没有进行复习，所以一开始还没有思路，全排序问题的核心在于回溯法。

这道题在我完成了全排列的算法（基础的交换法）之后，输出的可能不是字典序，这就需要到后面用一个sort函数来进排序。若需字典序，需修改算法：先预排序：先对输入数组排序（sort），再使用标记数组：在每一层递归中，按元素值从小到大选择未使用的元素（而非交换）或者使用 next_permutation函数。

回溯法（Backtracking）

全排列问题本质上是枚举所有可能的排列组合。回溯法是解决此类问题的经典方法，其核心思想是：

深度优先搜索（DFS） 遍历所有可能性
通过状态重置（回溯）探索不同分支
递归处理子问题

算法步骤

初始化：创建结果列表 result 存储所有排列(一般都是数组)
递归函数 backtrack(start)：
- 终止条件：当 start 等于数组长度时，表示已生成一个完整排列，将其加入结果集
- 遍历选择：从 start 位置开始遍历到数组末尾：(需要注意循环开始不为0而是start)
  - 做选择：交换 start 和 i 位置的元素
  - 递归：处理 start+1 位置
  - 撤销选择：交换回原状态（关键回溯步骤）
启动递归：从索引 0 开始

图示说明

以 [1,2,3] 为例：

初始: [1,2,3]
├─ 固定1: [1,2,3]
│  ├─ 固定2: [1,2,3] → 完成 [1,2,3]
│  └─ 交换2,3: [1,3,2] → 完成 [1,3,2]
├─ 交换1,2: [2,1,3]
│  ├─ 固定1: [2,1,3] → 完成 [2,1,3]
│  └─ 交换1,3: [2,3,1] → 完成 [2,3,1]
└─ 交换1,3: [3,2,1]
   ├─ 固定2: [3,2,1] → 完成 [3,2,1]
   └─ 交换2,1: [3,1,2] → 完成 [3,1,2]

C++ 代码实现

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        backtrack(nums, 0, result);
        return result;
    }

private:
    void backtrack(vector<int>& nums, int start, vector<vector<int>>& result) {
        // 递归终止条件：到达数组末尾，保存当前排列
        if (start == nums.size()) {
            result.push_back(nums); // 自动创建深拷贝
            return;
        }

        // 尝试将每个元素放到 start 位置
        for (int i = start; i < nums.size(); ++i) {
            // 1. 做选择：交换元素
            swap(nums[start], nums[i]);
            
            // 2. 递归处理下一个位置
            backtrack(nums, start + 1, result);
            
            // 3. 撤销选择：回溯（恢复状态）
            swap(nums[start], nums[i]);
        }
    }
};

代码详解

backtrack 函数：

参数：
- nums：当前排列状态（通过引用传递，避免拷贝开销）
- start：当前需要固定的起始位置
- result：存储所有有效排列
递归终止：当 start 等于数组长度时，保存当前排列
核心循环：
- 交换 start 和 i 位置的元素，使 nums[i] 固定在 start 位置
- 递归处理下一个位置 (start+1)
- 关键回溯：交换回原状态，确保后续分支不受影响

深拷贝处理：
- result.push_back(nums) 会自动创建 nums 的深拷贝
- 避免了保存指针或引用导致的数据污染

复杂度分析

时间复杂度： $O(n \times n!)$
- 共有 $n!$ 种排列
- 每次保存排列需要 $O(n)$ 时间（复制数组）
- 递归调用本身也有开销，但主导项仍是 $n \times n!$
空间复杂度： $O(n)$
- 递归栈深度为 $n$
- 不计结果存储空间（结果本身需要 $O(n \times n!)$ 空间）
- 交换操作使用常数额外空间

优化与变体

1. 使用 STL 算法

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> result;
    sort(nums.begin(), nums.end());
    do {
        result.push_back(nums);
    } while (next_permutation(nums.begin(), nums.end()));
    return result;
}

解释：next_permutation 是 C++ 标准库中的函数，其核心功能是：将当前序列重排为字典序中的下一个更大排列（若不存在更大的排列，则重置为最小字典序（字符按升序排序后形成的序列）排列并返回 false）

优点：代码简洁，利用标准库高效实现
缺点：需要先排序，且修改了输入数组顺序

2. 处理重复元素

当输入数组可能包含重复元素时：

先对数组排序
在回溯循环中跳过连续重复元素

// 在 backtrack 函数的 for 循环内添加
if (i > start && nums[i] == nums[i-1]) continue;

3. 不修改原数组的实现

通过额外记录已使用元素的状态（visited 数组）避免交换：

void backtrack(vector<int>& nums, vector<int>& path, vector<bool>& visited, 
              vector<vector<int>>& result) {
    if (path.size() == nums.size()) {
        result.push_back(path); // 保存当前排列
        return;                 // 回溯到上一层
    }

    for (int i = 0; i < nums.size(); ++i) {
        if (visited[i]) continue; // 跳过已使用的元素
        
        // 1. 做选择（标记 + 加入路径）
        visited[i] = true;        // 标记元素i已被使用
        path.push_back(nums[i]);  // 将元素加入当前路径
        
        // 2. 递归
        backtrack(nums, path, visited, result);
        
        // 3. 撤销选择
        path.pop_back();    // 从路径中移除最后加入的元素
        visited[i] = false; // 取消标记，允许其他分支使用！！！
    }
}

总结

回溯法是解决排列组合问题的核心方法，通过"选择-递归-撤销"三步曲系统探索所有可能性
状态重置（回溯）是关键：每次递归返回后必须恢复现场，确保后续分支的正确性
空间换时间：虽然结果存储需要 $O(n \times n!)$ 空间，但在约束条件下是必要且合理的

组栈、队列和stl习题