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]]
使用深度優(yōu)先搜索加遞歸
function permute(nums) {
var res = [];
var used = [];
var tmp = [];
helper(nums, tmp);
return res;
function helper(nums, tmp){
//已經(jīng)滿了就放到結(jié)果數(shù)組里并退出這層helper
if(tmp.length == nums.length){
res.push(tmp.concat());
} else {
for(var idx = 0; idx < nums.length; idx++){
// 遇到已經(jīng)加過的元素就跳過
if(used[idx]){
continue;
}
used[idx] = true;
tmp.push(nums[idx]);
//加入該元素后進(jìn)入下一層helper
//下一層helper還是從頭開始遍歷收夸，將第一個(gè)找到的沒用過的元素壓入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:
這次數(shù)組中可能有重復(fù)的元素，但是最后的組合不能是重復(fù)的吴超。
加一個(gè)判斷條件赂苗，如果后面的元素等于前面的元素爷恳，且前面的元素在本次結(jié)果中已經(jīng)使用了，那么這個(gè)后面的元素才可以用兽肤。
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;
};
