题解 | #没有重复项数字的全排列#
2022.0814算法第20题没有重复项数字的全排列
全排列采用递归回溯的思想，
递归是一种算法结构，回溯是一种算法思想
- 一个递归就是在函数中调用函数本身来解决问题。
回溯和DFS，其主要的区别是，回溯法在求解过程中不保留完整的树结构，而深度优先搜索则记下完整的搜索树。
递归回溯的思路还是挺好理解的，就是每次都走到底，走到叶子节点之后在返回进行其他路径的搜索，也就是回溯。
介绍的时候是需要用到栈数据存储方式的，先进后出。
递归就是利用系统调用栈完成数据存储。
全排列感觉和树的遍历还是不太一样的，全排列本身就是树的建立，获取每个叶子节点的路径。
DFS如果针对一棵树进行搜索，也就是前中后序搜索方法，也是采用递归的方式进行，也可以利用迭代的方法，显示声明数据栈进行搜索。
当树的结构不是二叉树的时候，根节点的子节点不确定数目，此时需要考虑节点的不重复性。
针对1、2、3全排列，首先选择1作为第一层的数据，然后选择第二层的2，在选择第三层的3；
此时一个叶子节点出现，进行回溯，返回第二层选择3，第三层选择2；（交换2和3）
出现叶子节点，在进行回溯，此时需要回溯到第一层选择2（交换1和2），第二层选择1，第三层选择3；
出现叶子节点，进行回溯，返回第二层选择3，第三层选择1（交换1和3）；
进行回溯，回溯到第一层选择3（交换1和3），第二层选择1，第三层选择2；
以此类推，获取全部的排列方式。
针对每次选择，代码中的体现就是交换两个数字，针对其他的问题也可以采用不同的方式进行处理。
还需要在研究多刷题。
void recursion(vector<vector<int> > &res,vector<int> &num,int index){
if(index==num.size()-1)
res.push_back(num);
else{
for(int i=index;i<num.size();i++){
swap(num[i], num[index]);
recursion(res, num, index+1);
swap(num[i], num[index]);
}
}
}
2022.0822补充
上面的方法，输出的顺序不是按照字典序进行输出的，
[3,2,1],[3,1,2]最后两个结果是反的。
个人认为上面的代码不好理解。
可以使用used数组标记当前值是否被使用过，这样的话思路就会更加明白。
在递归函数中，首先遍历整个需要排列的数组。
根据当前值是否已经排列，进行不同的操作。
如果当前值已经排列，则直接跳过；
如果还没有排列，则加入path数组，记录当前排列，并将当前值设置为已排列。
之后递归调用函数，将深度deepth+1，获取下一个排列数。
void recursion(vector<vector<int>> &res,vector<int> &num,int deepth,
vector<bool> used,vector<int> path){
//当深度为数组大小时，说明已经排列完成，将此种排列结果加入到结果数组中
if(deepth==num.size()){
//将此种排列结果加入到结果数组中
res.push_back(path);
return ;
}
//对num数组进行循环，每次循环找到一个排列数3，2，1
for(int i=0;i<num.size();i++){
//判断当前值是否已经排列，如果已经排列，直接跳过
if(used[i])
continue;
//如果还没排列，则更新状态，设置为已排列
used[i]=true;
//并且将当前值加入到排列数组中
path.push_back(num[i]);
//递归调用，找到下一层的可选择排列数
recursion(res, num, deepth+1, used, path);
//找到之后，需要回归到原来的状态，取出当前值
path.pop_back();
//并将当前值设置为未排列
used[i]=false;
}
}
这个方法获得顺序是按照字典序进行排列的。而且感觉这种协防更好理解。
投递完美世界等公司10个岗位 >