题目
给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
解答
感觉可以用递归做。。
python库
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
return list(itertools.permutations(nums))
Runtime: 36 ms, faster than 99.74% of Python3 online submissions for Permutations.
Memory Usage: 13.9 MB, less than 5.36% of Python3 online submissions for Permutations.
回溯算法
第一反应就是，一个个摁住数字，然后排序。回溯算法也这样
就是对这个树进行深度优先遍历。
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
if len(nums) == 0:
return []
used = [False]*len(nums)
res = []
Solution.__dfs(self, nums, 0, [], used, res)
return res
def __dfs(self, nums: List[int], index: int, pre: [int], used: [int], res: [int]):
if index == len(nums):
res.append(pre.copy())
return
for i in range(len(nums)):
if not used[i]:
used[i] = True
pre.append(nums[i])
Solution.__dfs(self, nums, index+1, pre, used, res)
used[i] = False
pre.pop()
Runtime: 44 ms, faster than 91.26% of Python3 online submissions for Permutations.
Memory Usage: 13.8 MB, less than 5.36% of Python3 online submissions for Permutations.
var permute = function(nums) {
if (nums.length === 0) {
return []
}
let used = new Array(nums.length)
for (let i = 0; i < used.length; i++) {
used[i] = false
}
let res = []
const dfs = function(nums, index, pre, used, res) {
if (index === nums.length) {
res.push(pre.slice())
return
}
for (let i in nums) {
if (!used[i]) {
used[i] = true
pre.push(nums[i])
dfs(nums, index + 1, pre, used, res)
used[i] = false
pre.pop()
}
}
}
dfs(nums, 0, [], used, res)
return res
};
Runtime: 72 ms, faster than 45.94% of JavaScript online submissions for Permutations.
Memory Usage: 36.4 MB, less than 48.00% of JavaScript online submissions for Permutations.
func permute(nums []int) [][]int {
if len(nums) == 0 {
return nil
}
res := make([][]int, 0)
dfs(nums, nil, &res)
return res
}
func dfs(nums []int, pre []int, res *[][]int) {
if len(nums) == 0 {
*res = append(*res, append([]int{}, pre...))
return
}
for i := range nums {
dfs(append(append([]int{}, nums[0:i]...), nums[i+1:]...), append(pre, nums[i]), res)
}
}
Runtime: 4 ms, faster than 92.03% of Go online submissions for Permutations.
Memory Usage: 7 MB, less than 100.00% of Go online submissions for Permutations.
递归
func permute(nums []int) [][]int {
var ret [][]int
var helper func(int)
helper = func(k int) {
if k == len(nums) {
tmp := make([]int, len(nums))
copy(tmp, nums)
ret = append(ret, tmp)
return
}
for i := k; i < len(nums); i++ {
nums[i], nums[k] = nums[k], nums[i]
helper(k + 1)
nums[i], nums[k] = nums[k], nums[i]
}
}
helper(0)
return ret
}
Runtime: 4 ms, faster than 92.03% of Go online submissions for Permutations.
Memory Usage: 7 MB, less than 100.00% of Go online submissions for Permutations.
var permute = function(nums) {
if (nums.length === 0) {
return []
}
let res = []
const helper = function(k) {
if (k === nums.length) {
res.push(nums.slice())
return
}
for (let i = k; i < nums.length; i++) {
[nums[i], nums[k]] = [nums[k], nums[i]]
helper(k + 1);
[nums[i], nums[k]] = [nums[k], nums[i]]
}
}
helper(0)
return res
};
Runtime: 68 ms, faster than 68.65% of JavaScript online submissions for Permutations.
Memory Usage: 36.8 MB, less than 24.00% of JavaScript online submissions for Permutations.
