高效遍历一个数组的所有排列组合情况 c++

以下是一种递归思路的实现方式：

void backtrack(vector<int>& nums, int start, vector<vector<int>>& res) {
    if(start == nums.size() - 1) { // 如果已经遍历到最后一个元素
        res.push_back(nums); // 将当前排列组合加入结果集中
        return;
    }
    for(int i = start; i < nums.size(); i++) { // 枚举当前元素和后面的元素
        swap(nums[start], nums[i]); // 将当前元素放到最前面
        backtrack(nums, start + 1, res); // 递归遍历后面的元素
        swap(nums[start], nums[i]); // 恢复原数组
    }
}

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> res;
    backtrack(nums, 0, res);
    return res;
}

算法思路：

1. 遍历数组中的所有元素，将当前元素与后面的元素进行交换，得到一种排列组合。
2. 用递归的方式遍历当前排列组合中后面的元素，得到所有排列组合。
3. 递归结束时，将当前排列组合加入结果集中。
4. 恢复原数组。

时间复杂度：$O(n \times n!)$，其中 $n$ 是数组长度。因为总共有 $n!$ 种排列组合，每种排列组合需要 $O(n)$ 的时间复杂度来交换数组中的元素。

空间复杂度：$O(n \times n!)$，其中 $n$ 是数组长度。因为总共有 $n!$ 种排列组合，每种排列组合的空间复杂度都是 $O(n)$