Permutation tree not making sense with the code

Question

I watched a youtube video where this basic permutation tree was shown. If you look at this bit of code:

    function recursion(input, set = [], result = []) {
        if (!input.length) {
           result.push([...set].join(''));
         }

        for (let i = 0; i < input.length; i++) {
            const newArr = input.filter((n, index) => index !== i);
            set.push(input[i]);
            recursion(newArr, set, result);
            set.pop();
         }
         return result.join(', ');
}

you can see that the base case (if statement) is at the top before the parameter nums is filtered. So, my whole question is how the tree and the code makes sense because for me the code would remove one too many digits from the set array. Becuase it pops an item of when returning and doesn't it return more than two times?

Answer 1

Does this log add clarity?

/ entering recursion with input = [1,2,3], set = [], result = []
| looping, i = 0
| adding  1 to set
|   / entering recursion with input = [2,3], set = [1], result = []
|   | looping, i = 0
|   | adding  2 to set
|   |   / entering recursion with input = [3], set = [1,2], result = []
|   |   | looping, i = 0
|   |   | adding  3 to set
|   |   |   / entering recursion with input = [], set = [1,2,3], result = []
|   |   |   | adding 123 to result
|   |   |   \ returning [123]
|   |   | removing  3 from set
|   |   \ returning [123]
|   | removing  2 from set
|   | looping, i = 1
|   | adding  3 to set
|   |   / entering recursion with input = [2], set = [1,3], result = [123]
|   |   | looping, i = 0
|   |   | adding  2 to set
|   |   |   / entering recursion with input = [], set = [1,3,2], result = [123]
|   |   |   | adding 132 to result
|   |   |   \ returning [123,132]
|   |   | removing  2 from set
|   |   \ returning [123,132]
|   | removing  3 from set
|   \ returning [123,132]
| removing  1 from set
| looping, i = 1
| adding  2 to set
|   / entering recursion with input = [1,3], set = [2], result = [123,132]
|   | looping, i = 0
|   | adding  1 to set
|   |   / entering recursion with input = [3], set = [2,1], result = [123,132]
|   |   | looping, i = 0
|   |   | adding  3 to set
|   |   |   / entering recursion with input = [], set = [2,1,3], result = [123,132]
|   |   |   | adding 213 to result
|   |   |   \ returning [123,132,213]
|   |   | removing  3 from set
|   |   \ returning [123,132,213]
|   | removing  1 from set
|   | looping, i = 1
|   | adding  3 to set
|   |   / entering recursion with input = [1], set = [2,3], result = [123,132,213]
|   |   | looping, i = 0
|   |   | adding  1 to set
|   |   |   / entering recursion with input = [], set = [2,3,1], result = [123,132,213]
|   |   |   | adding 231 to result
|   |   |   \ returning [123,132,213,231]
|   |   | removing  1 from set
|   |   \ returning [123,132,213,231]
|   | removing  3 from set
|   \ returning [123,132,213,231]
| removing  2 from set
| looping, i = 2
| adding  3 to set
|   / entering recursion with input = [1,2], set = [3], result = [123,132,213,231]
|   | looping, i = 0
|   | adding  1 to set
|   |   / entering recursion with input = [2], set = [3,1], result = [123,132,213,231]
|   |   | looping, i = 0
|   |   | adding  2 to set
|   |   |   / entering recursion with input = [], set = [3,1,2], result = [123,132,213,231]
|   |   |   | adding 312 to result
|   |   |   \ returning [123,132,213,231,312]
|   |   | removing  2 from set
|   |   \ returning [123,132,213,231,312]
|   | removing  1 from set
|   | looping, i = 1
|   | adding  2 to set
|   |   / entering recursion with input = [1], set = [3,2], result = [123,132,213,231,312]
|   |   | looping, i = 0
|   |   | adding  1 to set
|   |   |   / entering recursion with input = [], set = [3,2,1], result = [123,132,213,231,312]
|   |   |   | adding 321 to result
|   |   |   \ returning [123,132,213,231,312,321]
|   |   | removing  1 from set
|   |   \ returning [123,132,213,231,312,321]
|   | removing  2 from set
|   \ returning [123,132,213,231,312,321]
| removing  3 from set
\ returning [123,132,213,231,312,321]

You can see how I added the logging to your code in this snippet:

const log = (depth, message) => 
  console .log ('|   '.repeat (depth)  + message)


function recursion(input, set = [], result = [], depth = 0) {
    log (depth, `/ entering recursion with input = [${input}], set = [${set}], result = [${result}]`)
    if (!input.length) {
        log (depth, `| adding ${[...set].join('')} to result`)
        result.push([...set].join(''));
     }

    for (let i = 0; i < input.length; i++) {
        log (depth, `| looping, i = ${i}`)
        const newArr = input.filter((n, index) => index !== i);
        log (depth, `| adding  ${input[i]} to set` )
        set.push(input[i]);
        recursion(newArr, set, result, depth + 1);
        log (depth, `| removing  ${input[i]} from set` )
        set.pop();
    }
    log (depth, `\\ returning [${result}]`)
    return result.join(', ');
}

console .log (recursion([1, 2, 3]))

.as-console-wrapper {min-height: 100% !important; top: 0}

(but the console output there is limited to the last 50 lines.)