leetcode：46. 全排列

题目

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

示例：

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

解答 & 代码

递归回溯：
[中等] 46. 全排列 - 图1

  1. class Solution {
  2. private:
  3.     vector<vector<int>> resultList;    // 结果数组，存储所有可能的排列
  4.     vector<int> curResult;            // 当前得到的排列
  5.     // 递归回溯
  6.     void dfs(vector<int>& nums, int left)
  7.     {
  8.         // 递归结束条件：若当前已遍历完数组 nums，则将当前的排列存入结果数组
  9.         if(left == nums.size())
  10.             resultList.push_back(curResult);
  12.         for(int i = left; i < nums.size(); ++i)
  13.         {
  14.             // 做选择
  15.             swap(nums[left], nums[i]);            
  16.             curResult.push_back(nums[left]);
  17.             // 递归进入下一层决策树
  18.             dfs(nums, left + 1);
  19.             // 撤销选择
  20.             curResult.pop_back();
  21.             swap(nums[left], nums[i]);
  22.         }
  23.     }
  24. public:
  25.     vector<vector<int>> permute(vector<int>& nums) {
  26.         dfs(nums, 0);
  27.         return resultList;
  28.     }
  29. };

复杂度分析：设数组 nums 长为 n

  • 时间复杂度 O(n×n!)：数组 nums 的全排列共有 [中等] 46. 全排列 - 图2 种，要遍历所有可能的排列，找到一个排列 curResult 将其存入结果数组 resultList 的时间复杂度 O(n)
  • 空间复杂度 O(n)：递归深度为 O(n)

执行结果：

  1. 执行结果：通过
  3. 执行用时：4 ms, 在所有 C++ 提交中击败了 59.76% 的用户
  4. 内存消耗：7.6 MB, 在所有 C++ 提交中击败了 54.40% 的用户