## 题目地址

https://leetcode.com/problems/permutations/

## 题目描述

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

Example:

``````Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
``````

## 思路

``````class Solution {
public:
vector<vector<int>> permute(vector<int>& num) {
vector<vector<int>> res;
vector<int> out, visited(num.size(), 0);
permuteDFS(num, 0, visited, out, res);
return res;
}
void permuteDFS(vector<int>& num, int level, vector<int>& visited, vector<int>& out, vector<vector<int>>& res) {
if (level == num.size()) {res.push_back(out); return;}
for (int i = 0; i < num.size(); ++i) {
if (visited[i] == 1) continue;
visited[i] = 1;
out.push_back(num[i]);
permuteDFS(num, level + 1, visited, out, res);
out.pop_back();
visited[i] = 0;
}
}
};

``````

``````class Solution {
public:
vector<vector<int>> permute(vector<int>& num) {
vector<vector<int>> res;
permuteDFS(num, 0, res);
return res;
}
void permuteDFS(vector<int>& num, int start, vector<vector<int>>& res) {
if (start >= num.size()) res.push_back(num);
for (int i = start; i < num.size(); ++i) {
swap(num[start], num[i]);
permuteDFS(num, start + 1, res);
swap(num[start], num[i]);
}
}
};

``````

_ a1 _ a2 _ : a3a1a2, a1a3a2, a1a2a3

_ a2 _ a1 _ : a3a2a1, a2a3a1, a2a1a3

``````class Solution {
public:
vector<vector<int>> permute(vector<int>& num) {
if (num.empty()) return vector<vector<int>>(1, vector<int>());
vector<vector<int>> res;
int first = num[0];
num.erase(num.begin());
vector<vector<int>> words = permute(num);
for (auto &a : words) {
for (int i = 0; i <= a.size(); ++i) {
a.insert(a.begin() + i, first);
res.push_back(a);
a.erase(a.begin() + i);
}
}
return res;
}
};

``````

``````class Solution {
public:
vector<vector<int>> permute(vector<int>& num) {
vector<vector<int>> res{{}};
for (int a : num) {
for (int k = res.size(); k > 0; --k) {
vector<int> t = res.front();
res.erase(res.begin());
for (int i = 0; i <= t.size(); ++i) {
vector<int> one = t;
one.insert(one.begin() + i, a);
res.push_back(one);
}
}
}
return res;
}
};

``````

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

``````

## 关键点解析

• 回溯法
• backtrack 解题公式

## 代码

• 语言支持： Javascript, Python3

JavaScript Code:

``````/*
* @lc app=leetcode id=46 lang=javascript
*
* [46] Permutations
*
* https://leetcode.com/problems/permutations/description/
*
* algorithms
* Medium (53.60%)
* Total Accepted:    344.6K
* Total Submissions: 642.9K
* Testcase Example:  '[1,2,3]'
*
* Given a collection of distinct integers, return all possible permutations.
*
* Example:
*
*
* Input: [1,2,3]
* Output:
* [
* ⁠ [1,2,3],
* ⁠ [1,3,2],
* ⁠ [2,1,3],
* ⁠ [2,3,1],
* ⁠ [3,1,2],
* ⁠ [3,2,1]
* ]
*
*
*/
function backtrack(list, tempList, nums) {
if (tempList.length === nums.length) return list.push([...tempList]);
for(let i = 0; i < nums.length; i++) {
if (tempList.includes(nums[i])) continue;
tempList.push(nums[i]);
backtrack(list, tempList, nums);
tempList.pop();
}
}
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function(nums) {
const list = [];
backtrack(list, [], nums)
return list
};
``````

Python3 Code:

``````class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
"""itertools库内置了这个函数"""
return itertools.permutations(nums)

def permute2(self, nums: List[int]) -> List[List[int]]:
"""自己写回溯法"""
res = []
def _backtrace(nums, pre_list):
if len(nums) <= 0:
res.append(pre_list)
else:
for i in nums:
# 注意copy一份新的调用，否则无法正常循环
p_list = pre_list.copy()
p_list.append(i)
left_nums = nums.copy()
left_nums.remove(i)
_backtrace(left_nums, p_list)
_backtrace(nums, [])
return res
``````

Python Code:

``````class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
"""itertools库内置了这个函数"""
import itertools
return itertools.permutations(nums)

def permute2(self, nums: List[int]) -> List[List[int]]:
"""自己写回溯法"""
res = []
def _backtrace(nums, pre_list):
if len(nums) <= 0:
res.append(pre_list)
else:
for i in nums:
# 注意copy一份新的调用，否则无法正常循环
p_list = pre_list.copy()
p_list.append(i)
left_nums = nums.copy()
left_nums.remove(i)
_backtrace(left_nums, p_list)
_backtrace(nums, [])
return res

def permute3(self, nums: List[int]) -> List[List[int]]:
"""回溯的另一种写法"""
res = []
length = len(nums)
def _backtrack(start=0):
if start == length:
# nums[:] 返回 nums 的一个副本，指向新的引用，这样后续的操作不会影响已经已知解
res.append(nums[:])
for i in range(start, length):
nums[start], nums[i] = nums[i], nums[start]
_backtrack(start+1)
nums[start], nums[i] = nums[i], nums[start]
_backtrack()
return res
``````

评论
0 评论