This is a review of backtracking and putting this algorithm together in its simplest form, which is still complex with many different factors at play.
The complexity of backtracking starts with the arguments passed into the function. In its simplest form backtracking for permutations includes:
result // a result array of arrays
current // contains the current elements of each permutation
nums // the actual numbers to be permutated
With these three arguments for the backtracking callback we then either check if the current
permutation elements are the same length as the nums
array as the base case to exit.
Or loop through the nums array making sure there are unique elements on the current
permutation candidate, to then add new elements to current
from nums
and then remove them as we exit the recursions.
var permute = function(nums) {
let result = []
backtracking(result, [], nums)
return result
};
const backtracking = (result, current, nums) => {
if(current.length === nums.length){
result.push([...current]) // add a copy of current
}else{
for(let i = 0; i <nums.length; i++){
if(current.includes(nums[i])) continue // skip rest of loop
current.push(nums[i])
backtracking(result, current, nums)
current.pop()
}
}
}
Current permutations array
This array (current
) will only store the elements if we define it in the local scope of backtracking, but also we have to create a new array in this case with the spread operator when we enter the base case.
Top comments (0)