DEV Community

Santiago Salazar Pavajeau
Santiago Salazar Pavajeau

Posted on

Simplest permutations

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
Enter fullscreen mode Exit fullscreen mode
current // contains the current elements of each permutation
Enter fullscreen mode Exit fullscreen mode
nums // the actual numbers to be permutated
Enter fullscreen mode Exit fullscreen mode

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()
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

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)