javascriptarraysarraylistpermutationbacktracking

Backtracking confusion


Concerning Javascript, I've been trying to understand backtracking lately and it's really confusing. Specifically, I've been trying to understand the permutation problem, which when given an array, we want all of the possible permutations of that array:

function permute(nums) {
    let result = [];
    function backtrack(temp = []) {
        if (temp.length === nums.length) {
            result.push([...temp]);  
            return;
    }
        for (let i = 0; i < nums.length; i++) {
            if (temp.includes(nums[i])) continue;  
            temp.push(nums[i]);       
            backtrack(temp);          
            temp.pop();               
    }
  }
  backtrack();
  return result;
}

Let's consider nums = [1,2] for simplicity. \

From what I understand, we start at temp=[], at i=0 temp -> [1], and backtrack is supposed to search for the other possible values (just 2). It ignores the deletion of the supposed value in temp.pop() and goes back to the loop where i=1 now and temp [1] -> [1,2] and now that it satisfies the condition of length, a copy of this temp array is appended to the result array. So my question is, what happens after this appending?

Supposedly, the code provided above does return [[1,2],[2,1]], which is correct but I don't understand why. After the appending, apparently we pop the final value from temp, now it's at [1] and we restart the loop in i, since we finished it to obtain [1,2]. We go through i=0 again, but temp already has the value 1 so we continue. Then it gets added 2 again, and the backtrack sends this result to check the initial condition of length, isn't it? Apparently, it must pop twice and start the loop at i=1 for the backtrack to have backtrack([2]) and then search for the missing 1.

I don't understand where my flaw is but I know there is some misinterpretation somewhere, I just don't understand where.


Solution

  • We go through i=0 again, but temp already has the value 1 so we continue

    Not exactly. Once you pop() after dealing with [1, 2], you don't look at i = 0 again for that permutation. Once you've finished looking at [1, 2], your previous backtrack call was looking at i=1, and so when you pop(), your loop completes its iterations, and you go back to the previous backtrack call that added [1] (which has an i=0). This then calls pop() again, setting temp back to an empty array, where your loop then iterates to i=1 where you push 2, the backtrack call then pushes 1 to give you [2, 1], which gets added to your result on the subsequent backtrack call. Here's a tree view of the nested backtrack calls in action which might help (see first note, which is where your misunderstanding seems to be):

    backtrack([])
    ├─ i=0 -> push 1 -> temp = [1]
    │  └─ backtrack([1])
    │     ├─ i=0 -> skip (1 in temp)
    │     ├─ i=1 -> push 2 -> temp = [1,2]
    │     │  └─ backtrack([1,2]) -> add [1,2] to `result`
    │     └─ pop -> temp = [1] (note: here, i=1, so loop finishes)
    └─ pop -> temp = []
    
    ├─ i=1 -> push 2 -> temp = [2]
    │  └─ backtrack([2])
    │     ├─ i=0 -> push 1 -> temp = [2,1]
    │     │  └─ backtrack([2,1]) -> add [2,1] to `result`
    │     ├─ pop -> temp = [2]
    │     └─ i=1 -> skip (2 in temp) [note: after this, the loop finishes)
    └─ pop -> temp = []