# 46. Permutations 全排列

@TOC

## # 题目描述

Given a collection of distinct numbers, return all possible permutations.

For example,

``````[1,2,3] have the following permutations:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
``````

## # 解题方法

### # 方法一：库函数

``````from itertools import permutations
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
return list(permutations(nums))
``````

C++中也有next_permutation函数，但是注意需要先排序。

``````class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
do {
res.push_back(nums);
} while (next_permutation(nums.begin(), nums.end()));
return res;
}
};
``````

### # 方法二：递归

Python代码如下：

``````class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
self.dfs(nums, res, [])
return res

def dfs(self, nums, res, path):
if not nums:
res.append(path)
else:
for i in xrange(len(nums)):
self.dfs(nums[:i] + nums[i + 1:], res, path + [nums[i]])
``````

### # 方法三：回溯法

C++版本的代码如下：

``````class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
const int N = nums.size();
vector<vector<int>> res;
vector<int> path;
vector<int> visited(N, 0);
dfs(nums, 0, visited, res, path);
return res;
}
private:
void dfs(vector<int>& nums, int pos, vector<int>& visited, vector<vector<int>>& res, vector<int>& path) {
const int N = nums.size();
if (pos == N) {
res.push_back(path);
return;
}
for (int i = 0; i < N; i++) {
if (!visited[i]) {
visited[i] = 1;
path.push_back(nums[i]);
dfs(nums, pos + 1, visited, res, path);
path.pop_back();
visited[i] = 0;
}
}
}
};
``````

Python代码如下：

``````class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
visited = [0] * len(nums)
res = []

def dfs(path):
if len(path) == len(nums):
res.append(path)
else:
for i in range(len(nums)):
if not visited[i]:
visited[i] = 1
dfs(path + [nums[i]])
visited[i] = 0

dfs([])
return res
``````

## # 日期

2018 年 2 月 24 日 2018 年 12 月 14 日 —— 12月过半，2019就要开始 2019 年 9 月 25 日 —— 做梦都在秋招，这个秋天有毒