Leetcode:46. 全排列、47. 全排列 II(C++)

Source

目录

46. 全排列

问题描述:

实现代码与解析:

回溯:

原理思路:

47. 全排列 II

题目描述:

实现代码与解析:

回溯:

原理思路:


46. 全排列

问题描述:

        给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1:

输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2:

输入:nums = [0,1]
输出:[[0,1],[1,0]]

示例 3:

输入:nums = [1]
输出:[[1]]

实现代码与解析:

回溯:

class Solution {
public:
    vector<int> path;//记录路径
    vector<vector<int>> result;//记录结果
    void backtracking(vector<int> nums,vector<int> used)
    {
        //全部遍历完了
        if(path.size()==nums.size())
        {
            result.push_back(path);
            return;
        }
        for(int i=0;i<nums.size();i++)
        {
            //跳过已经使用过的
            if(used[i]==1) continue;
            used[i]=1;
            path.push_back(nums[i]);//处理
            backtracking(nums,used);//递归
            path.pop_back();//回溯
            used[i]=0;//回溯
        }
    }
    vector<vector<int>> permute(vector<int>& nums) 
    {
        vector<int> used(nums.size(),0);//初始化为0
        backtracking(nums,used);
        return result;
    }
};

原理思路:

        此题寻找的是全排列组合,所以我们每次遍历都要重头开始寻找,而不是向后去循环,所以显然不能重复去循环一个数,所以我们用一个used数组去记录已经用过的数,再次遇到时就跳过此次循环即可。

47. 全排列 II

题目描述:

        给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。

例 1:

输入:nums = [1,1,2]
输出:
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2:

输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

实现代码与解析:

回溯:

class Solution {
public:
    vector<int> path;//记录路径
    vector<vector<int>> result;//记录结果
    void backtracking(vector<int> nums,vector<int> used)
    {
        //全部遍历完了
        if(path.size()==nums.size())
        {
            result.push_back(path);
            return;
        }
        for(int i=0;i<nums.size();i++)
        {
            //数层上去重
            if(i>0&&nums[i]==nums[i-1]&&used[i-1]==0) continue;
            //树枝上跳过已经用过的数
            if(used[i]==1) continue;
            used[i]=1;
            path.push_back(nums[i]);//处理
            backtracking(nums,used);//递归
            path.pop_back();//回溯
            used[i]=0;//回溯
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) 
    {
        vector<int> used(nums.size(),0);
        sort(nums.begin(),nums.end());
        backtracking(nums,used);
        return result;
    }
};

原理思路:

        在上一题的基础上,仅仅多了一个树层去重的逻辑,当然这样写要先排序。

//数层上去重
if(i>0&&nums[i]==nums[i-1]&&used[i-1]==0) continue;

        其实最重要的就是理解为什么要加上used[i-1]=0,因为我们这里是树层上的去重,确保的是当前层循环不出现同样的数,而在不同层上是可以出现同样的数,若与此次循环相同的上一个数是在上一层循环就用过的数,那么此层循环就可以取这个数,所以要加上这个逻辑。为什么以往的题就不用加呢,因为以往的题递归都是从i+1的逻辑开始遍历,本身就避免了这种情况,大家可以仔细想一想。