LeetCode 剑指 Offer II 083. 没有重复元素集合的全排列

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

示例 1：

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

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

解法一：直接使用STL：

class Solution {
public:vector<vector<int>> permute(vector<int>& nums) {// next_permutation函数每次产生下一个排列// 下一个排列的含义是按字典顺序下一个更大的排列// 因此需要先对nums进行从小到大排序sort(nums.begin(), nums.end());vector<vector<int>> ans;do {ans.push_back(nums);} while (next_permutation(nums.begin(), nums.end()));return ans;}
};

如果输入数组大小为n，此算法时间复杂度为O（n*n!），空间复杂度为O（1）。next_permutation函数的时间复杂度最多为O（n）。

解法二：回溯法，遍历某个排列的每一个元素，当遍历到下标i时，我们遍历所有可以放到下标i的元素，但有些元素在前面已经用过了，因此我们维护一个visited数组，如果该元素没有用过，才放到下标i：

class Solution {
public:vector<vector<int>> permute(vector<int>& nums) {vector<vector<int>> ans;unordered_set<int> visited;vector<int> current;backtrack(0, current, nums, visited, ans);return ans;}private:void backtrack(int pos, vector<int> current, vector<int> &nums, unordered_set<int> &visited, vector<vector<int>> &ans) {int sz = nums.size();if (pos == sz) {ans.push_back(current);}for (int i = 0; i < sz; ++i) {if (visited.find(nums[i]) != visited.end()) {continue;}visited.insert(nums[i]);current.push_back(nums[i]);backtrack(pos + 1, current, nums, visited, ans);current.pop_back();visited.erase(nums[i]);}}
};

如果输入数组大小为n，此算法时间复杂度为O（n*n!），空间复杂度为O（n）。backtrack函数的调用次数为O（n!），每次调用中，会循环n次。对于空间复杂度，递归深度为n，主要开销是栈空间开销和current、visited数组开销。

解法三：在解法二中，我们使用了visited数组来标记哪些元素已经被全排列过了，我们可以直接修改nums数组，当遍历到下标i时，我们可以令[0,i]的所有元素都是已经全排列过的元素，具体做法是将当前循环中要排列的元素和下标为i的元素交换：

class Solution {
public:vector<vector<int>> permute(vector<int>& nums) {vector<vector<int>> ans;backtrack(0, nums, ans);return ans;}private:void backtrack(int pos, vector<int> &nums, vector<vector<int>> &ans) {int sz = nums.size();if (pos == sz) {ans.push_back(nums);}for (int i = pos; i < sz; ++i) {swap(nums[i], nums[pos]);backtrack(pos + 1, nums, ans);swap(nums[i], nums[pos]);}}
};

如果输入数组大小为n，此算法时间复杂度为O（n*n!），空间复杂度为O（n）。backtrack函数的调用次数为O（n!），每次调用中，会循环n次。对于空间复杂度，递归深度为n，主要开销是栈空间开销。