LeetCode：全排列

妖狐艹你老母 2021-11-11 06:02 275阅读 0赞

## 全排列（一） ##

[leetcode题目链接][leetcode]  
给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:
    
    输入: [1,2,3]
    输出:
    [
      [1,2,3],
      [1,3,2],
      [2,1,3],
      [2,3,1],
      [3,1,2],
      [3,2,1]
    ]

> 实现思路：使用DFS深搜， num.pop\_back()这句很关键，以例子\[1, 2, 3\]输入为例。  
> 第一次满足 if(count == len) 语句的num数组为\[1, 2, 3\]，这时需要num退栈。  
> 退到2这一步骤，由于3已经访问过，所以V\[1, 2, 3\]值都为1不满足，这时说明应该继续退栈，  
> 执行num.pop\_back()操作，退到1，由于2已经访问过，此时访问3即可。生成\[1 ,3 ,2\]序列，其他类似。

class Solution {
    public:
        vector<vector<int>> res;
        vector<int> num;
        int V[100] = {0};
        int len = 0;
        vector<vector<int>> permute(vector<int>& nums) {
            len = nums.size();
            fun(0, nums);
            return res;
        }
        int fun(int count, vector<int>& nums)
        {
            if(count == len)
            {
                res.push_back(num);
                return 0;
            }
            for(int i = 0; i < nums.size(); i++)
            {
                if(V[i] == 0)
                {
                    num.push_back(nums[i]);
                    V[i] = 1;
                    fun(count + 1, nums);
                    V[i] = 0;
                    num.pop_back();
                }
            }
            return 0;
        }
    };

## 全排列（二） ##

[全排列2][2]  
给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:
    
    输入: [1,1,2]
    输出:
    [
      [1,1,2],
      [1,2,1],
      [2,1,1]
    ]

class Solution {
    public:
    	vector<vector<int>> res;
    	vector<int> num;
    	map<int, int> V;
    	vector<vector<int>> permuteUnique(vector<int>& nums) {
    
    		fun(0, nums);
    		return res;
    	}
    	int fun(int count, vector<int>& nums)
    	{
            map<int, bool> M;  //必须为局部变量
    		if (count == nums.size())
    		{
    			res.push_back(num);
    			return 0;
    		}
    		for (int i = 0; i < nums.size(); i++)
    		{
    			if (!V[i] && !M[nums[i]])
    			{
    				V[i] = true;
                    M[nums[i]] = true;
    				num.push_back(nums[i]);
    				fun(count + 1, nums);
    				V[i] = false;
                    num.pop_back();
    			}
    		}
    		return 0;
    	}
    };

[leetcode]: https://leetcode-cn.com/problems/permutations/
[2]: https://leetcode-cn.com/problems/permutations-ii/