class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
}
};
46. 全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1] 输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1] 输出：[[1]]
提示：
1 <= nums.length <= 6-10 <= nums[i] <= 10nums 中的所有整数 互不相同原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 2.7 MB, 提交时间: 2021-07-22 11:27:41
func permute(nums []int) (ans [][]int) {
var backtrack func([]int, []int)
backtrack = func(li, temp []int) {
if len(li) == 0 {
ans = append(ans, temp)
return
}
for i := 0; i < len(li); i++ {
n_li := make([]int, len(li)-1)
for j := 0; j < len(li) - 1; j++ {
if j < i {
n_li[j] = li[j]
} else {
n_li[j] = li[j+1]
}
}
backtrack(n_li, append(temp, li[i]))
}
}
backtrack(nums, []int{})
return
}
python3 解法, 执行用时: 36 ms, 内存消耗: 15.2 MB, 提交时间: 2021-07-22 11:06:50
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
ans = []
def backtrack(li: List[int], tmp: List[int]):
if not li:
ans.append(tmp)
return
for i in range(len(li)):
backtrack(li[:i] + li[i+1:], tmp + li[i:i+1])
backtrack(nums, [])
return ans
python3 解法, 执行用时: 44 ms, 内存消耗: 13.7 MB, 提交时间: 2020-12-03 17:22:57
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
# 回溯搜索的全排列
res = []
def backtrack(nums, tmp):
if not nums:
res.append(tmp)
return
for i in range(len(nums)):
backtrack(nums[:i] + nums[i+1:], tmp + nums[i:i+1])
backtrack(nums, [])
return res