給一組整數(shù)提揍，返回所有可能的排列
faster than 92%
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function(nums) {
var v = nums.slice()
//var sub = []
var res = []
permuteDFS(nums, v, 0, [], res)
return res
};
var permuteDFS = function(nums, v, flag, sub, res){
if(flag === nums.length){
res.push(sub.slice())
}else{
for(var i = 0; i < nums.length; ++i){
if(v[i] === nums[i]){
v[i] = 'a'
sub.push(nums[i])
permuteDFS(nums, v, flag + 1, sub, res)
sub.pop()
v[i] = nums[i]
}
}
}
}
遞歸是一種算法結(jié)構(gòu)，回溯是一種算法思想。
遞歸是在函數(shù)中調(diào)用函數(shù)本身來(lái)解決問(wèn)題夜惭，回溯是通過(guò)不同的嘗試來(lái)生成問(wèn)題的解，類似與窮舉铛绰，和窮舉法不同的是回溯會(huì)剪枝诈茧，對(duì)已經(jīng)知道錯(cuò)誤的結(jié)果沒(méi)有必要再枚舉接下來(lái)的答案了，是一種對(duì)搜索過(guò)程的優(yōu)化捂掰。
每次交換兩個(gè)值的解法敢会，從左到右曾沈，僅使用當(dāng)前索引字符交換其右側(cè)的每個(gè)字符，此方案是谷歌面試的標(biāo)準(zhǔn)最佳解決方案鸥昏。
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function(nums) {
var res = []
permuteDFS(nums, 0, res)
return res
};
var permuteDFS = function(nums, flag, res){
if(flag === nums.length){
res.push([...nums])
} else {
for(var i = flag; i < nums.length; i++){
swap(nums, flag, i)
permuteDFS(nums, flag + 1, res)
swap(nums, flag, i)
}
}
}
var swap = function(nums, i, j){
var temp = nums[i]
nums[i] = nums[j]
nums[j] = temp
}
