46 Permutations
Given a collection of distinct numbers, return all possible permutations.
For example,[1,2,3] have the following permutations:
[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
使用深度优先搜索加递归
function permute(nums) {
var res = [];
var used = [];
var tmp = [];
helper(nums, tmp);
return res;
function helper(nums, tmp){
//已经满了就放到结果数组里并退出这层helper
if(tmp.length == nums.length){
res.push(tmp.concat());
} else {
for(var idx = 0; idx < nums.length; idx++){
// 遇到已经加过的元素就跳过
if(used[idx]){
continue;
}
used[idx] = true;
tmp.push(nums[idx]);
//加入该元素后进入下一层helper
//下一层helper还是从头开始遍历,将第一个找到的没用过的元素压入tmp
helper(nums, tmp);
tmp.pop();
used[idx] = false;
}
}
}
}
47. Permutations II
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
这次数组中可能有重复的元素,但是最后的组合不能是重复的。
加一个判断条件,如果后面的元素等于前面的元素,且前面的元素在本次结果中已经使用了,那么这个后面的元素才可以用。
var permuteUnique = function(nums) {
var res = [];
var used = [];
var num = nums.length;
nums.sort();
var help = function(temp) {
//console.log(temp);
if (temp.length===nums.length) {
res.push(temp.concat());
} else {
for (var i = 0;i < num;i++) {
if (used[i]===true)
continue;
if (nums[i]===nums[i-1]&&used[i-1]!==true)
continue;
used[i] = true;
temp.push(nums[i]);
help(temp);
temp.pop();
used[i] = false;
}
}
};
help([]);
return res;
};
网友评论