Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
思路：
這道題是之前那道 Permutations 全排列的延伸懒熙，由于輸入數(shù)組有可能出現(xiàn)重復(fù)數(shù)字缓苛，如果按照之前的算法運(yùn)算邦鲫，會(huì)有重復(fù)排列產(chǎn)生，我們要避免重復(fù)的產(chǎn)生，在遞歸函數(shù)中要判斷前面一個(gè)數(shù)和當(dāng)前的數(shù)是否相等秃流，如果相等碳默，前面的數(shù)必須已經(jīng)使用了宝磨，即對(duì)應(yīng)的visited中的值為1，當(dāng)前的數(shù)字才能使用翰舌，否則需要跳過(guò)嚣潜，這樣就不會(huì)產(chǎn)生重復(fù)排列了，代碼如下：
var permute = function(nums) {
var res = [];
var out = [];
var visited = [];
nums.sort((a,b)=>a-b)
for (var i = 0; i < nums.length; i++) {
visited[i] = 0;
}
permuteDFS(nums, 0, out, res, visited);
return res;
function permuteDFS(nums, pos, out, res, visited) {
var tmp = out.concat();
if (pos === nums.length) res.push(tmp);
else {
for (var i = 0; i < nums.length; i++) {
if (visited[i] === 0) {
if(i>0 && nums[i]===nums[i-1] && visited[i-1]==0) continue;
visited[i] = 1;
out.push(nums[i]);
permuteDFS(nums, pos + 1, out, res, visited);
out.pop();
visited[i] = 0;
}
}
}
}
};
