leetcode 链接：全排列

题目

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

示例：

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

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

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

解答 & 代码

递归回溯

• 时间复杂度 O(n×n!)：全排列需要遍历 O(n!) 种可能的排列，找到每个排列（result）后需要 O(n) 的时间将其复制到答案数组 resultList 中

• 空间复杂度 O(n)：递归深度为 O(n)

  class Solution {
    // 交换数组中的两个元素
    void swap(vector<int>& nums, int idx1, int idx2)
    {
        int temp = nums[idx1];
        nums[idx1] = nums[idx2];
        nums[idx2] = temp;
    }
  
    // 递归回溯求全排列
    void calPermute(vector<int>& nums, int left, int right, vector<int>& result, vector<vector<int>>& resultList)
    {
        for(int i = left; i <= right; ++i)
        {
            swap(nums, i, left);            // 将数组第 i 个元素交换到 left 位置上
            result.push_back(nums[left]);    // 将这个值作为排列的第 left 个元素
  
            if(left + 1 > right)            // 得到一个完整排列，插入 resultsList
                resultList.push_back(result);
            else                            // 递归求 left+1 ~ right 位置的全排列
                calPermute(nums, left + 1, right, result, resultList);
  
            // 回溯，撤销上面做的改变
            swap(nums, i, left);
            result.pop_back();
        }
    }
  public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> resultList;
        int len = nums.size();
        if(len <= 1)            //  特殊情况：数组只有 0 or 1 个元素，直接返回
        {
            resultList.push_back(nums);
            return resultList;
        }
  
        vector<int> result;
        calPermute(nums, 0, len - 1, result, resultList);
        return resultList;
    }
  };
  

  执行结果： ``` 执行结果：通过

执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户 内存消耗：7.3 MB, 在所有 C++ 提交中击败了 91.98% 的用户 ```