全排列:给定一个没有重复数字的序列,返回其所有可能的全排列。
解法:全排列必定是用回溯法,但是又分成了一种是在原数组里面进行不同位置上元素的交换,另一种是普通的回溯法了,从某个位置出发,用visited数组标记是否已经被并入。
vector<vector<int>> permute(vector<int>& nums) {
//使用回溯法,不断交换两个位置上的数
//注意对每个位置上的元素都有不交换(自己跟自己交换,跟后面的位置上的元素进行交换的情况)
vector<vector<int>> ret;
//从0号位开始
permuteCore(nums,ret,0);
return ret;
}
void permuteCore(vector<int>& nums,vector<vector<int>>& ret,int index){
if(index == nums.size()){
ret.push_back(nums);
}
for(int i=index;i<nums.size();i++){
swap(nums[index],nums[i]);
permuteCore(nums,ret,index+1);
swap(nums[index],nums[i]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
全排列用回溯法
//建立标记数组
vector<vector<int>> ret;
for(int i=0;i<nums.size();i++){
vector<bool> visited(nums.size(),false);
vector<int> currVec;
currVec.push_back(nums[i]);
visited[i] = true;
permuteCore(nums,visited,currVec,ret);
}
return ret;
}
void permuteCore(vector<int>& nums,vector<bool>& visited,
vector<int>& currVec,vector<vector<int>>& ret){
if(currVec.size() == nums.size()){
//如果长度相等,说明已经加入完毕
ret.push_back(currVec);
return ;
}
//否则还要继续遍历剩下的节点,然后加入
for(int i=0;i<nums.size();i++){
if(visited[i]==false){
//还没有加入
currVec.push_back(nums[i]);
visited[i] = true;
permuteCore(nums,visited,currVec,ret);
visited[i] = false;
currVec.pop_back();
}
}
}