Leetcode46: 全排列

2021年4月8日 138Browse 1Like 0Comments

题目描述

给定一个 没有重复 数字的序列,返回其所有可能的全排列。

示例:

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

解题思路

这道题不涉及巧妙头疼的算法,只是单纯的考察递归回溯的编程技巧。

我们以示例数据为例,分析一下我们的思路,力求清晰易懂。

[1,2,3]的全排列怎么求呢?按照我们高中学的排列组合的知识,全排列的求解相当于在_ _ _三个位置上依次选择一个数字填入。在第一个位置可以选择1,2,3中的任意一个,第二个位置可以选择除去第一个位置选择的数字之外的所有数字,第三个位置只能选择剩下的唯一一个数字。比如,如果第一个位置选择1,2,3中的1,那么第二个位置可以选择2,3中的一个任意一个,假设选择3,那么第三个位置就只能选择2。

上述过程就是求解全排列的过程,然后我们思考怎么用递归的方式去模拟这一过程。

为了避免选择之前位置已经选择的数字,我们使用一个visited数组去记录当前数字是否已经被选择。我们用path数组去记录一个排列,res数组去记录最终答案。用一个for循环去模拟一个位置选择不同数字的过程,不同位置的切换用递归的特性去模拟。最后最重要的就是回溯的过程,当递归结束的时候,当前的状态需要重置,也就是visited数组对应位置置为false,path数组将该数字退出。

然后还有一个不可或缺的部分就是获得答案的过程:

if(path.size()==nums.size())
{
    res.push_back(path);
    return;
}

示例代码

void DFS(vector<int>&nums,vector<bool>&visited,vector<vector<int>>&res,vector<int>&path)
{
    if(path.size()==nums.size())
    {
        res.push_back(path);
        return;
    }
    for(int i=0;i<nums.size();++i)
    {
        if(!visited[i])
        {
            visited[i]=true;
            path.push_back(nums[i]);
            DFS(nums,visited,res,path);
            visited[i]=false;
            path.pop_back();
        }
    }
}

vector<vector<int>> permute(vector<int>& nums)
{
    vector<vector<int>>res;
    vector<int>path;
    vector<bool>visited(nums.size(),false);
    DFS(nums,visited,res,path);
    return res;
}

agedcat_xuanzai

这个人很懒,什么都没留下

Comments