46. 全排列【回溯算法】
给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [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 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
写好一个交换
然后开始谈思路，就是n从0开始递增，算第n个位置存的数，确定好之后存num进结果v
之后再swap原路恢复，进入下一种情况。
进行回溯
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]);
}
}
};LeetCode排名第一的代码
使用了栈和状态存储的bool值
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;
}
}
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-12-07 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录