解析

//! n*n!,n -> 共n!个排列，每个需要O(n)时间复杂度；忽视返回值占用，空间复杂度O(n)
class Solution {
public:
  vector<vector<int>> permute(vector<int> &nums) {
    bitset<10> numsStatus; //输入规模最大是7
    vector<int> resPart;
    vector<vector<int>> res;
    backtrack(nums, numsStatus, resPart, res);
    return res;
  }
  void backtrack(vector<int> &nums, bitset<10> &numsStatus,
                 vector<int> &resPart, vector<vector<int>> &res) {
    if (resPart.size() == nums.size()) {
      res.emplace_back(resPart);
      return;
    }
    for (int i = 0; i < nums.size(); ++i) {
      if (numsStatus[i] == false) {
        resPart.emplace_back(nums[i]);
        numsStatus[i] = true;
        backtrack(nums, numsStatus, resPart, res);
        resPart.pop_back();
        numsStatus[i] = false;
      }
    }
  }
};

// n*n!,1 -> 字典序法通常比回溯法更快，因为它避免了递归调用栈的开销，并且返回结果是有序的
class Solution {
public:
  vector<vector<int>> permute(vector<int> &nums) {
    vector<vector<int>> res;
    sort(nums.begin(), nums.end());
    do {
      res.emplace_back(nums);
    } while (nextPermutation(nums));
    return res;
  }
  bool nextPermutation(vector<int> &nums) {
    int n = nums.size();

    int changePoint = n - 2;
    while (changePoint >= 0 && nums[changePoint] > nums[changePoint + 1]) {
      --changePoint;
    }
    if (changePoint < 0) {
      return false;
    }

    int changePointBigger = n - 1;
    while (changePointBigger >= 0 &&
           nums[changePointBigger] <= nums[changePoint]) {
      --changePointBigger;
    }
    swap(nums[changePoint], nums[changePointBigger]);
    reverse(nums.begin() + changePoint + 1, nums.end());
    return true;
  }
};