全排列 II #19
Description
题目
出处：LeetCode 算法第47题
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ]
思路
相比于上一题，本题的元素是可以重复的，所以我们需要一个数组来保存当前的项是否已经添加了
解答
var permuteUnique = function (nums) {
if (nums.length === 0) {
return [];
}
var result = [];
var resultStr = [];
var used = [];
var temp = [];
DFS(nums, result, temp, used, resultStr);
return result;
};
function copy(array) {
var result = [];
for (var i = 0, len = array.length; i < len; i++) {
result.push(array[i]);
}
return result;
}
function DFS(nums, result, temp, used, resultStr) {
if (temp.length === nums.length) {
if (resultStr.indexOf(temp.join(',')) < 0) {
result.push(copy(temp));
resultStr.push(temp.join(','));
}
};
for (var i = 0; i < nums.length; i++) {
if (used[i]) {
continue
}
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue
}
used[i] = true;
temp.push(nums[i]);
DFS(nums, result, temp, used, resultStr);
used[i] = false;
temp.pop();
}
}