Question 198896 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – Solving leetcode #46 Permutations

I’m trying to solve leetcode #46 Permutations. The question is:

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Here is a solution in JavaScript to the problem:

let permute = function(nums) {
    if(nums.length === 0) return [nums];
    let res = [], len = nums.length,used = new Array(len).fill(false);

    let backtrack = function(currPermutation){
        if(currPermutation.length === nums.length){
            res.push([...currPermutation]);
            return;
        }

        for(let i = 0; i < len; ++i){
            if(used[i]) continue;

            currPermutation.push(nums[i]);
            console.log("curr perm = ",currPermutation);
            used[i] = true;
            backtrack(currPermutation);
            currPermutation.pop();
            used[i] = false;
        }
    }

    backtrack([]);
    return res;
};

permute([1,2,3]);

For the input nums = [1,2,3] here is the result of the console.log("curr perm = ",currPermutation:

curr perm =  [ 1 ]
curr perm =  [ 1, 2 ]
curr perm =  [ 1, 2, 3 ]
curr perm =  [ 1, 3 ]
curr perm =  [ 1, 3, 2 ]
curr perm =  [ 2 ]
curr perm =  [ 2, 1 ]
curr perm =  [ 2, 1, 3 ]
curr perm =  [ 2, 3 ]
curr perm =  [ 2, 3, 1 ]
curr perm =  [ 3 ]
curr perm =  [ 3, 1 ]
curr perm =  [ 3, 1, 2 ]
curr perm =  [ 3, 2 ]
curr perm =  [ 3, 2, 1 ]

What I don’t understand is when curr perm = [1,2,3] why does it pop the number 2 instead of number 3, same thing when curr perm = [2,1,3] why does it pop 1 instead of 3 and obviously same thing when curr perm = [3,1,2] why does it pop 1 instead of 2?

Tags:

2

Answers


  1. 0

    The popping of the numbers happens in reverse order because the code explores the possibilities in a depth-first manner. It means that it first goes as deep as possible in one direction before backtracking and exploring other options.

    So, when currPermutation is [1,2,3], the code pops the number 2 first because it has already explored all the possibilities with 1 as the first element and 2 as the second element. It needs to backtrack to try other options, which is why 2 is popped before exploring other numbers.

    Similarly, for [2,1,3], the code pops 1 before exploring other numbers because it has already explored all the possibilities with 2 as the first element and 1 as the second element.

    Login or Signup to reply.
  2. 0

    when curr perm = [1,2,3] why does it pop the number 2 instead of number 3?

    It does pop the number 3: there are two consecutive pop() calls happening (as recursion unwinds) and one push (where you have your console.log).

    All this will become clearer if you also log the pop actions, and add some indentation to reflect how deep we are in the recursion tree:

    let permute = function(nums) {
    if(nums.length === 0) return [nums];
    let res = [], len = nums.length,used = new Array(len).fill(false);

    let backtrack = function(currPermutation, indent="") {
        if(currPermutation.length === nums.length){
            console.log(`${indent}found permutation: ${currPermutation}`);
            res.push([...currPermutation]);
            return;
        }

        for(let i = 0; i < len; ++i){
            if(used[i]) continue;

            currPermutation.push(nums[i]);
            console.log(`${indent}pushed ${nums[i]} to permutation: ${currPermutation}`);
            used[i] = true;
            backtrack(currPermutation, indent + "  ");
            currPermutation.pop();
            console.log(`${indent}popped ${nums[i]} from permutation: ${currPermutation}`);
            used[i] = false;
        }
    }

    backtrack([]);
    return res;
};

permute([1,2,3]);
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search