47. Permutations II
給定一個可能包含重複數字的數組 nums，返回所有可能的唯一排列，順序不限。
範例 1：
輸入：nums = [1,1,2]
輸出：
[[1,1,2],
[1,2,1],
[2,1,1]]
Python
from typing import List
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
def backtrack(start=0):
if start == len(nums):
result.append(nums[:])
return
seen = set()
for i in range(start, len(nums)):
if nums[i] in seen:
continue
seen.add(nums[i])
nums[start], nums[i] = nums[i], nums[start]
backtrack(start + 1)
nums[start], nums[i] = nums[i], nums[start]
result = []
nums.sort()
backtrack()
return result
16.72MB, 51ms
C++
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end()); // Sort the numbers to handle duplicates
backtrack(nums, 0, result);
return result;
}
private:
void backtrack(vector<int>& nums, int start, vector<vector<int>>& result) {
if (start == nums.size()) {
result.push_back(nums);
return;
}
set<int> seen; // Set to track elements to avoid duplicates at the current position
for (int i = start; i < nums.size(); ++i) {
if (seen.count(nums[i]) == 0) {
seen.insert(nums[i]);
swap(nums[start], nums[i]);
backtrack(nums, start + 1, result);
swap(nums[start], nums[i]); // Swap back to restore the original order
}
}
}
};
11.95MB, 6ms
Javascript
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permuteUnique = function(nums) {
const result = [];
nums.sort((a, b) => a - b); // Sort the numbers to handle duplicates
backtrack(nums, 0, result);
return result;
};
function backtrack(nums, start, result) {
if (start === nums.length) {
result.push([...nums]);
return;
}
const seen = new Set(); // Set to track elements to avoid duplicates at the current position
for (let i = start; i < nums.length; i++) {
if (!seen.has(nums[i])) {
seen.add(nums[i]);
[nums[start], nums[i]] = [nums[i], nums[start]]; // Swap
backtrack(nums, start + 1, result);
[nums[start], nums[i]] = [nums[i], nums[start]]; // Swap back to restore the original order
}
}
}
55.2MB, 90ms
