46. 全排列(Permutations)M
英文题目
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
Example 1:
Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Example 2:
Input: nums = [0,1] Output: [[0,1],[1,0]]
Example 3:
Input: nums = [1] Output: [[1]]
Constraints:
1 <= nums.length <= 6
-10 <= nums[i] <= 10
All the integers of nums are unique.
中文题目
给定一个 没有重复 数字的序列,返回其所有可能的全排列。
示例:
输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
回溯
时间复杂度 O(n x n!),空间复杂度O(n)
# python3: 时间 56 ms, 击败 8.64%; 内存 16.1 MB, 击败 56.26% class Solution: def permute(self, nums: List[int]) -> List[List[int]]: self.res = [] used = [False] * len(nums) self.backtrack(nums, [], used) return self.res def backtrack(self, nums: List[int], path: List[int], used: List[bool]) -> None: if len(nums) == len(path): self.res.append(path[:]) return for i in range(len(nums)): if used[i]: continue used[i] = True path.append(nums[i]) self.backtrack(nums, path, used) path.pop() used[i] = False
// c++: 时间 4 ms, 击败 68.51%; 内存 7.6 MB, 击败 70.13% class Solution { public: vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>> res; vector<int> path; vector<bool> used(nums.size(), false); backtrack(res, nums, path, used); return res; } void backtrack(vector<vector<int>> &res, const vector<int> &nums, vector<int> &path, vector<bool> &used) { if (nums.size() == path.size()) { res.push_back(path); return; } for (int i = 0; i < nums.size(); ++i) { if (used[i]) { continue; } used[i] = true; path.push_back(nums[i]); backtrack(res, nums, path, used); path.pop_back(); used[i] = false; } } };
// java: 时间 0 ms, 击败 100%; 内存 42.7 MB, 击败 33.38% class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> res = new ArrayList<>(); List<Integer> path = new ArrayList<>(); boolean[] used = new boolean[nums.length]; Arrays.fill(used, false); backtrack(res, nums, path, used); return res; } private void backtrack(List<List<Integer>> res, int[] nums, List<Integer> path, boolean[] used) { if (path.size() == nums.length) { // 注意结果要 new 一个新arraylist res.add(new ArrayList<Integer>(path)); return; } for (int i = 0; i < nums.length; ++i) { if (used[i]) { continue; } used[i] = true; path.add(nums[i]); backtrack(res, nums, path, used); path.remove(path.size()-1); used[i] = false; } } }
// go: 时间 0 ms, 击败 100%; 内存 2.5 MB, 击败 90.70% func permute(nums []int) [][]int { res := make([][]int, 0) path := make([]int, 0, len(nums)) used := make([]bool, len(nums)) backtrack(&res, nums, path, used) return res } func backtrack(res *[][]int, nums []int, path []int, used []bool) { if len(nums) == len(path) { tmp := make([]int, len(nums)) copy(tmp, path) *res = append(*res, tmp) } for i := 0; i < len(nums); i++ { if used[i] { continue } used[i] = true path = append(path, nums[i]) backtrack(res, nums, path, used) path = path[:len(path)-1] used[i] = false } }
// javascript: 时间 80 ms, 击败 40.37%; 内存 44.6 MB, 击败 14.25% /** * @param {number[]} nums * @return {number[][]} */ var permute = function(nums) { const res = new Array(); const path = new Array(); const used = new Array(nums.length).fill(false); backtrack(res, nums, path, used); return res; }; const backtrack = function(res, nums, path, used) { if (nums.length == path.length) { res.push(Array.from(path)); return; } for (let i = 0; i < nums.length; ++i) { if (used[i]) { continue; } used[i] = true; path.push(nums[i]); backtrack(res, nums, path, used); path.pop(); used[i] = false; } }