47. 全排列 II(Permutations II)M
英文题目
Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.
Example 1:
Input: nums = [1,1,2] Output: [[1,1,2], [1,2,1], [2,1,1]]
Example 2:
Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Constraints:
1 <= nums.length <= 8
-10 <= nums[i] <= 10
中文题目
给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。
示例 1:
输入:nums = [1,1,2] 输出: [[1,1,2], [1,2,1], [2,1,1]]
示例 2:
输入:nums = [1,2,3] 输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
提示:
1 <= nums.length <= 8
-10 <= nums[i] <= 10
回溯
时间复杂度 O(n x n!),空间复杂度O(n)
# python3: 时间 44 ms, 击败 89.75%; 内存 16.1 MB, 击败 67.5 class Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]: self.res = [] used = [False] * len(nums) nums.sort() 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 elif i > 0 and nums[i] == nums[i-1] and used[i-1] == False: continue used[i] = True path.append(nums[i]) self.backtrack(nums, path, used) path.pop() used[i] = False
// c++: 时间 8 ms, 击败 61.48%; 内存 8.3 MB, 击败 87.84% class Solution { public: vector<vector<int>> permuteUnique(vector<int>& nums) { vector<vector<int>> res; vector<int> path; vector<bool> used(nums.size(), false); sort(nums.begin(), nums.end()); 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; } else if (i > 0 && nums[i] == nums[i-1] && used[i-1] == false) { continue; } used[i] = true; path.push_back(nums[i]); backtrack(res, nums, path, used); path.pop_back(); used[i] = false; } } };
// java: 时间 1 ms, 击败 99.65%; 内存 42.7 MB, 击败 54.66% class Solution { public List<List<Integer>> permuteUnique(int[] nums) { List<List<Integer>> res = new ArrayList<>(); List<Integer> path = new ArrayList<>(); boolean[] used = new boolean[nums.length]; Arrays.fill(used, false); Arrays.sort(nums); 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; } else if (i > 0 && nums[i] == nums[i-1] && used[i-1] == false) { 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%; 内存 3.5 MB, 击败 95.14% func permuteUnique(nums []int) [][]int { res := make([][]int, 0) path := make([]int, 0, len(nums)) used := make([]bool, len(nums)) sort.Ints(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 } else if i > 0 && nums[i] == nums[i-1] && used[i-1] == false { continue } used[i] = true path = append(path, nums[i]) backtrack(res, nums, path, used) path = path[:len(path)-1] used[i] = false } }
// javascript: 时间 64 ms, 击败 97.68%; 内存 44 MB, 击败 67.18% /** * @param {number[]} nums * @return {number[][]} */ var permuteUnique = function(nums) { const res = new Array(); const path = new Array(); const used = new Array(nums.length).fill(false); nums.sort((a,b) => a-b); 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; } else if (i > 0 && nums[i] == nums[i-1] && used[i-1] == false) { continue; } used[i] = true; path.push(nums[i]); backtrack(res, nums, path, used); path.pop(); used[i] = false; } }