给定一个没有重复数字的序列,返回其所有可能的全排列。
示例:
输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/permutations 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> v;
back(nums,v,0);
return v;
}
void swap(int &a,int &b){
int t=a;
a=b;
b=t;
}
void back(vector<int>& nums ,vector<vector<int>>& v,int n){
if(n==nums.size())v.push_back(nums);
for(int i=n;i<nums.size();i++){
swap(nums[i],nums[n]);
back(nums,v,n+1);
swap(nums[i],nums[n]);
}
}
};
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> ret;
int len = nums.size();
if (len == 0) {
return ret;
}
bool visit[len] = {false};
stack<int> s;
dev(len, 0, ret, nums, visit, s);
return ret;
}
void dev(int len, int current, vector<vector<int>>& ret, vector<int>& nums, bool *visit, stack<int> &s) {
vector<int> temp;
if (current == len) {
int* end = &s.top() + 1;
int* begin = end - s.size();
vector<int> temp(begin, end);
ret.push_back(temp);
return;
}
for (int i = 0; i < len; i++) {
if (!visit[i]) {
s.push(nums[i]);
visit[i] = true;
dev(len, current + 1, ret, nums, visit, s);
s.pop();
visit[i] = false;
}
}
}
};