Leetcode46. 全排列

题目描述

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

示例:

1
2
3
4
5
6
7
8
9
10
输入: [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数组将该数字退出。

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

1
2
3
4
5
if(path.size()==nums.size())
{
    res.push_back(path);
    return;
}

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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;
}