AcWing 51. C++:回溯法(简单易懂)
原题链接
中等
作者:
上下求索
,
2021-02-03 19:10:24
,
所有人可见
,
阅读 355
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> permutation(vector<int>& nums) {
int n=nums.size();
bool visited[n];
memset(visited,0,sizeof visited);
vector<int> trace;
backtrace(nums,trace,0,visited);
return res;
}
// idx 用来表示 trace 的 idx 位置存放nums中未被访问过的数
void backtrace(vector<int>& nums,vector<int>& trace,int idx,bool visited[])
{
/*找到一个可行解*/
if(idx==nums.size()){
res.push_back(trace);
return;
}
/*枚举选择列表*/
unordered_map<int,int> rec;
for(int i=0;i<nums.size();++i)
{
if(!visited[i])
{
// 剪枝:同层次此元素已使用多次,在使用必然会照成重复全排列,所以直接跳过
if(rec.count(nums[i]))continue;
/*choose过程:将nums[i]加入idx的位置*/
visited[i]=1;
trace.push_back(nums[i]);
/*进入下一步决策:idx+1的位置上插入新的值*/
backtrace(nums,trace,idx+1,visited);
/*unchoose过程:将nums[i]移除在idx这个位置上*/
visited[i]=0;
trace.pop_back();
// 标记这个元素已经使用过了
rec[nums[i]]=1;
}
}
}
};