全排列一

题目描述

算法原理

• 我们先把决策树画出来，根据决策树写代码，然后设计函数头

• 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;
    }
   
};