【LeetCode 每日一题】46. 全排列 | 手写图解版思路 + 代码讲解
谢玄xx:
up,对数组后续元素进行dfs遍历后,为什么还需要pop_back()呢?combine数组不是一直在往前走吗?这一点不太清楚
【回复】dfs之后说明当前这个位置选择这个数字的所有组合已经搜索完了,需要尝试换一个数字,所以需要把刚刚push进去的数字删除
【回复】噢噢,combine要清空才能存放下一个数组...没事了,感谢up!
泥奏凯哒哒:
up请问我这段代码为什么不行呢?
为什么需要下面这个两行代码(加上后就正确了)?
path.pop_back();
control.erase(i);
在回溯后不是会自动恢复调用前的状态吗, 我这里的control和path并不是全局变量或者引用类型,不理解呀
【回复】class Solution {
public:
vector<vector<int>>ans;
void get_all_ans(vector<int>& nums , set<int>control, vector<int>path, unsigned int lev)
{
//可行解
if(lev==nums.size())
{
ans.push_back(path);
return;
}
for(unsigned int i=0;i<nums.size();++i)
{
//是否非重复路径
if(control.find(i)==control.end())
{
//路径缓存
path.push_back(nums【i】);
control.insert(i);
get_all_ans(nums,control,path,lev+1);
/* 加上这两句代码程序才正确
path.pop_back();
control.erase(i);*/
}
}
}
vector<vector<int>> permutation(vector<int>& nums) {
set<int>control;
vector<int>path;
get_all_ans(nums,control,path,0);
return ans;
}
};
高高果实:
谢谢分享, 投币了, up是我目前看过所有题解和视频中,讲得最详细最明白的[给心心]
EchoDot999:
请问下为什么dfs里的for循环是从i=0开始而不是i=idx开始呢[笑哭]
【回复】如果用的是那种交换的思路,就是i=idx,但是视频不是用的那种