46.全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

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

输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：

输入：nums = [1]
输出：[[1]]

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

来源：力扣（LeetCode）
链接：https:///problems/permutations

class Solution {
public:
    void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len){
        // 所有数都填完了
        if (first == len) {
            res.emplace_back(output);
            return;
        }
        for (int i = first; i < len; ++i) {
            // 动态维护数组
            swap(output[i], output[first]);
            // 继续递归填下一个数
            backtrack(res, output, first + 1, len);
            // 撤销操作
            swap(output[i], output[first]);
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > res;
        backtrack(res, nums, 0, (int)nums.size());
        return res;
    }
};

这段代码实现了回溯算法来生成给定整数数组 nums 的所有可能排列。permute 函数接受输入数组 nums，并返回一个向量的向量 res，其中每个内部向量表示输入数组的一个唯一排列。

backtrack 函数是一个辅助函数，通过交换输入数组中的元素递归地生成所有排列。函数接受四个参数：向量的向量 res，用于存储每个排列的向量 output，表示当前递归调用的起始索引的整数 first，以及表示输入数组长度的整数 len。

递归的基本情况是当 first 索引等于输入数组的长度 len 时。此时，所有元素都已交换，当前排列已完成，因此它将被添加到结果向量 res 中。

在递归情况下，函数遍历从 first 到 len-1 的所有索引，并交换当前索引处的元素和 first 索引处的元素。这生成一个新的排列，其中 first 索引处的元素被固定，其余元素递归地进行排列。一旦递归调用返回，函数就会交换元素以恢复输入数组的原始顺序。

总的来说，这段代码使用回溯算法生成了输入数组的所有可能排列。该算法的时间复杂度是 O(n!)，其中 n 是输入数组的长度，因为有 n! 种排列要生成。