Generating permutations of the input sequence using backtracking

Question

I am practicing for interviews on Leetcode and one of the questions is:

Given an array of numbers, you need to generate all the possible permutations. For better understanding, I turned to the solutions, one of which is like this:

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
       List<List<Integer>> list = new ArrayList<>();
       // Arrays.sort(nums); // not necessary
       backtrack(list, new ArrayList<>(), nums);
       return list;
    }

    private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){
       if(tempList.size() == nums.length){
          list.add(new ArrayList<>(tempList));
       } else{
          for(int i = 0; i < nums.length; i++){ 
             if(tempList.contains(nums[i])) 
                 continue;
             System.out.println("Adding: "+nums[i]);
             tempList.add(nums[i]);
             backtrack(list, tempList, nums);
             System.out.println("Removing: "+nums[i]);
             tempList.remove(tempList.size() - 1);
          }
       }
    } 
}

The two print statements show me how the numbers are added and removed (and consequently the permutations generated):

Adding: 1
Adding: 2
Adding: 3
Removing: 3
Removing: 2
--------> why is 1 not removed here?
Adding: 3
Adding: 2
Removing: 2
Removing: 3
Removing: 1
Adding: 2
Adding: 1
Adding: 3
Removing: 3
Removing: 1
Adding: 3
Adding: 1
Removing: 1
Removing: 3
Removing: 2
Adding: 3
Adding: 1
Adding: 2
Removing: 2
Removing: 1
Adding: 2
Adding: 1
Removing: 1
Removing: 2
Removing: 3

While I understood how it is adding and removing the numbers, I'm not sure why it is working that way. As per my understanding, after generating the first permutation <1,2,3>, all these three numbers should be removed. But that is not the case. Only <2,3> are removed, leaving 1 behind. Why is it so? I would appreciate any help.

Answer 1

Normal processing - add next number until we hit the limit.

Adding: 1

Adding: 2

Adding: 3

We hit the ceiling, record the 1,2,3 perm and back-track, removing3

Removing: 3

We exit the backtrack(3) call and, as we just added 2 we immediately remove it.

Removing: 2

We now continue the loop that added 2 and try 3 in the second position.

Adding: 3

The list now contains 1,3.

We now loop for the third entry and find that 2 is not in the list yet.

Adding: 2

It will add 1,3,2 to the result list.

The balanced removal of 2.

Removing: 2

etc.