全排列一
题目描述
算法原理
我们先把决策树画出来，根据决策树写代码，然后设计函数头
dfs函数用途就是从nums数组选数填入横线
就是有三个位置，我们把1 2 3填进这三个位置，而且保证不重复。
比如我们第一冷选了1之后第二轮就不能选1了，打个红色的×。我们人的智慧一眼就知道前面选了1之后就不能选1了但是机器要怎么实现这一点呢？我们可以通过一个visited 数组实现这一点。
如我们把visted数组全设为false 当 添加一个之后再设置为true
我们还需要 path这个vector数组用来保存遍历的路径，ret 数组用来保证path每次遍历的结果
class Solution {
public:
vector<int>path;
vector<vector<int>>ret;
int visted[7];
void dfs(vector<int>& nums)
{
if (path.size() == nums.size())
{
ret.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++)
{
if (visted[i] != true)
{
path.push_back(nums[i]);
visted[i] = true;
dfs(nums);
visted[i] = false;
path.pop_back();
}
// else
// {
// return ;
// }
}
}
vector<vector<int>> permute(vector<int>& nums) {
dfs(nums);
return ret;
}
};
魔鬼细节一：dfs（nums）后面的内容可以写在if外吗？
比如说下面这样
class Solution {
public:
vector<int>path;
vector<vector<int>>ret;
int visted[7];
void dfs(vector<int>& nums)
{
if (path.size() == nums.size())
{
ret.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++)
{
if (visted[i] != true)
{
path.push_back(nums[i]);
visted[i] = true;
}
dfs(nums);
visted[i] = false;
path.pop_back();
}
}
vector<vector<int>> permute(vector<int>& nums) {
dfs(nums);
return ret;
}
};
不可以因为这样会死递归
我们第二层还是从1开始的，1已经被遍历过了不会被if击中，就走下一层，下一次也是从1开始的，又走下一层。所以会死递归
从逻辑上解释只有我们上一层选择了一个数，下一层才开始选数
魔鬼细节二：我们剪枝的时候 可以用return吗？
比如下面这样
class Solution {
public:
vector<int>path;
vector<vector<int>>ret;
int visted[7];
void dfs(vector<int>& nums)
{
if (path.size() == nums.size())
{
ret.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++)
{
if (visted[i] != true)
{
path.push_back(nums[i]);
visted[i] = true;
dfs(nums);
visted[i] = false;
path.pop_back();
}
else
{
return ;
}
}
}
vector<vector<int>> permute(vector<int>& nums) {
dfs(nums);
return ret;
}
};
不可以，从代码执行的角度：我们从第二层返回到一层时，没有把所用情况遍历完，就把visted【i】，path恢复了。从逻辑上是希望第一层，最到最后一层才返回，而不是第二层有不符合条件的就返回第一层
#全排列二
题目描述
这道题和上一题唯一的区别就时nums数组元素可以重复了
比如 【1，1，2】 情况就没有 6种了
算法原理：
- 和第一题差不多只是剪枝不一样
- 当第一数选择 1 剩下 的数 112 和从第二位数选择1 剩下的数选择112 情况是一样的。
- 下图蓝色的×表示 同一层相同两个数一样时应该跳过
- 紫色的×表示一个数不能重复的选
代码实现
class Solution {
public:
vector<int> path;
vector<vector<int>> ret;
int visted[20];
void dfs(vector<int>&nums)
{
if(path.size() == nums.size())
{
ret.push_back(path);
return ;
}
for(int i = 0; i < nums.size(); i++)
{
if(visted[i] == false && ( i == 0|| nums[i] != nums[i-1] || visted[i-1] == true))
{
path.push_back(nums[i]);
visted[i] = true;
dfs(nums);
path.pop_back();
visted[i] = false;
}
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(),nums.end());
dfs(nums);
return ret;
}
};
