class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
}
};
47. 全排列 II
给定一个可包含重复数字的序列 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原站题解
rust 解法, 执行用时: 4 ms, 内存消耗: 2.1 MB, 提交时间: 2023-09-15 15:08:21
impl Solution {
pub fn permute_unique(nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut v: Vec<Vec<i32>> = Vec::new();
let len = nums.len();
let mut sum = Vec::new();
let mut book = vec![false; nums.len()];
Solution::helper(&mut sum, &nums, len, &mut v, &mut book);
v
}
pub fn helper(sum: &mut Vec<i32>,nums: &Vec<i32>,len: usize,
v: &mut Vec<Vec<i32>>,book: &mut Vec<bool>) {
if sum.len() == len {
v.push(sum.to_vec());
return;
}
let mut val = Vec::new();
for i in 0..len {
if !book[i] && !val.contains(&nums[i]) {
val.push(nums[i]);
book[i] = true;
sum.push(nums[i]);
Solution::helper(sum, nums, len, v, book);
book[i] = false;
sum.pop();
}
}
}
}
rust 解法, 执行用时: 4 ms, 内存消耗: 2.3 MB, 提交时间: 2023-09-15 15:06:18
impl Solution {
pub fn permute_unique(nums: Vec<i32>) -> Vec<Vec<i32>> {
fn dfs(
nums: &Vec<i32>,
idx: usize,
used: &mut Vec<bool>,
path: &mut Vec<i32>,
ans: &mut Vec<Vec<i32>>,
) {
if idx == nums.len() {
ans.push(path.to_vec());
return;
}
for (i, &x) in nums.iter().enumerate() {
if used[i] || i > 0 && !used[i - 1] && nums[i] == nums[i - 1] {
continue;
}
path.push(x);
used[i] = true;
dfs(nums, idx + 1, used, path, ans);
used[i] = false;
path.pop();
}
}
let mut nums = nums;
nums.sort();
let mut ans = Vec::new();
dfs(
&nums,
0,
&mut vec![false; nums.len()],
&mut vec![],
&mut ans,
);
ans
}
}
cpp 解法, 执行用时: 12 ms, 内存消耗: 8.9 MB, 提交时间: 2023-09-15 15:05:47
class Solution {
vector<int> vis;
public:
void backtrack(vector<int>& nums, vector<vector<int>>& ans, int idx, vector<int>& perm) {
if (idx == nums.size()) {
ans.emplace_back(perm);
return;
}
for (int i = 0; i < (int)nums.size(); ++i) {
if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
continue;
}
perm.emplace_back(nums[i]);
vis[i] = 1;
backtrack(nums, ans, idx + 1, perm);
vis[i] = 0;
perm.pop_back();
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> perm;
vis.resize(nums.size());
sort(nums.begin(), nums.end());
backtrack(nums, ans, 0, perm);
return ans;
}
};
java 解法, 执行用时: 1 ms, 内存消耗: 42.8 MB, 提交时间: 2023-09-15 15:05:23
class Solution {
boolean[] vis;
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
List<Integer> perm = new ArrayList<Integer>();
vis = new boolean[nums.length];
Arrays.sort(nums);
backtrack(nums, ans, 0, perm);
return ans;
}
public void backtrack(int[] nums, List<List<Integer>> ans, int idx, List<Integer> perm) {
if (idx == nums.length) {
ans.add(new ArrayList<Integer>(perm));
return;
}
for (int i = 0; i < nums.length; ++i) {
if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
continue;
}
perm.add(nums[i]);
vis[i] = true;
backtrack(nums, ans, idx + 1, perm);
vis[i] = false;
perm.remove(idx);
}
}
}
javascript 解法, 执行用时: 64 ms, 内存消耗: 44.3 MB, 提交时间: 2023-09-15 15:05:10
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permuteUnique = function(nums) {
const ans = [];
const vis = new Array(nums.length).fill(false);
const backtrack = (idx, perm) => {
if (idx === nums.length) {
ans.push(perm.slice());
return;
}
for (let i = 0; i < nums.length; ++i) {
if (vis[i] || (i > 0 && nums[i] === nums[i - 1] && !vis[i - 1])) {
continue;
}
perm.push(nums[i]);
vis[i] = true;
backtrack(idx + 1, perm);
vis[i] = false;
perm.pop();
}
}
nums.sort((x, y) => x - y);
backtrack(0, []);
return ans;
};
golang 解法, 执行用时: 4 ms, 内存消耗: 3.5 MB, 提交时间: 2023-09-15 15:04:55
func permuteUnique(nums []int) (ans [][]int) {
sort.Ints(nums)
n := len(nums)
perm := []int{}
vis := make([]bool, n)
var backtrack func(int)
backtrack = func(idx int) {
if idx == n {
ans = append(ans, append([]int(nil), perm...))
return
}
for i, v := range nums {
if vis[i] || i > 0 && !vis[i-1] && v == nums[i-1] {
continue
}
perm = append(perm, v)
vis[i] = true
backtrack(idx + 1)
vis[i] = false
perm = perm[:len(perm)-1]
}
}
backtrack(0)
return
}
php 解法, 执行用时: 12 ms, 内存消耗: 15.7 MB, 提交时间: 2021-05-13 10:18:22
class Solution {
/**
* @param Integer[] $nums
* @return Integer[][]
*/
function permuteUnique($nums) {
sort($nums);
$res = [];
$this->__backtrack($nums, [], $res);
return $res;
}
function __backtrack(array $nums, array $temp=[], array &$res=[])
{
if ( empty($nums) ) {
$res[] = $temp;
return;
} else {
for ( $i = 0; $i < count($nums); $i++ ) {
if ( $i > 0 && $nums[$i] == $nums[$i-1] ) continue;
$this->__backtrack(array_merge(array_slice($nums, 0, $i), array_slice($nums, $i+1)), array_merge($temp, [$nums[$i]]), $res);
}
}
}
}
python3 解法, 执行用时: 1040 ms, 内存消耗: 13.8 MB, 提交时间: 2020-12-02 10:33:56
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
# 回溯搜索的全排列
res = []
def backtrack(nums, tmp):
if not nums and tmp not in res:
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
python3 解法, 执行用时: 912 ms, 内存消耗: 13.7 MB, 提交时间: 2020-11-14 14:15:14
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
ans = []
for k in itertools.permutations(nums):
if list(k) not in ans:
ans.append(list(k))
return ans