1

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.

Improve this question
2
  • 1
    Does the output make more sense if I add some spaces? Commented Jul 31, 2017 at 15:53
  • @Dukeling, yes, this is wonderful. :) I got a bit of it. But it would be very helpful if I understand how the code does it. Commented Jul 31, 2017 at 15:56

3 Answers 3

Reset to default
1

Your logic seems has problem, as after addition of 1,2,3 in list and you are backtracking twice only as per recursion so 1 will always be part of your list. 

In Backtracking,
1
1->2
1->2->3
Remove 3 as no further element
Remove 2 from temp list but after this permute 2,3 ->3,2 
There is no need to remove all elements in single iteration over all elements, 
you can try with 4 input [1,2,3,4], will be more clear as many permutations will be 
there after removal of 2 as 2->3->4, 2->4->3.

Please find below alternate solution 

public static void permutate() {
    int[] nums = new int[] { 1, 2, 3 };
    backTrack(nums, 0, nums.length - 1);
}

public static void backTrack(int[] str, int l, int r) {
   if (l == r) {
    System.out.print("\n");
    for (int ele : str) {
     System.out.print(ele);
    }
    } else {
        for (int i = l; i <= r; i++) {
            str = swap(str, l, i);
            backTrack(str, l + 1, r);
            str = swap(str, l, i);
        }
    }
}

public static int[] swap(int[] a, int i, int j) {
 int temp = a[i];
 a[i] = a[j];
 a[j] = temp;
 return a;
}

If needed you can collect all permutation is any of the collection for further use.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

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.

Improve this answer

1 Comment

Got your point. Thank you. Sometimes this recursion makes my head spin! ;)
0

Well, I'll tried to explain this

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);
      }
   }
}

You start your backTracking, for each tab it's different recursion level, and each level has your own local variables (in this case 'i')

backtracking([empty list],[],[1,2,3])
   start for i = 0
   add to temp list nums[0] = 1
   call backtracking
   backtracking([],[1],[1,2,3])
      start for i = 0 // the other for it's waiting
      if(tempList.contains(nums[i])) //its true, then not add nums[0]
      now for i = 1
      add to temp list nums[1] = 2
      call backtracking
      backtracking([],[1,2],[1,2,3])
          start for i = 0 // the other two 'for' waiting
          if(tempList.contains(nums[i]))// true for nums[0],nums[1]
          now for i = 2
          add to temp list nums[2] = 3
          call backtracking
          backtracking([],[1,2,3],[1,2,3])
              if(tempList.size() == nums.length)//it's true
              //we have one permutation [1,2,3]
              //add templist in list
              finish this level of recursion, return to last level
          now for i = 3 then end recursion and remove
          tempList.remove(tempList.size() - 1);//after this templist = [1,2]
      now here the important part!!
      here remove again
      tempList.remove(tempList.size() - 1); // after this templist = [1]

      now i = 2 //see in this level before i = 1
      then the for continue
      add to temp list nums[2] = 3
      tempList = [1,3]//see that you first add 3 before delete 1
      call backtracking
      backtracking([],[1,3],[1,2,3])
          repeat process...
          here only we can add nums[1]
          add to temp list nums[1] = 2
          tempList = [1,3,2]
          call backtracking
          backtracking([],[1,3,2],[1,2,3])
              if(tempList.size() == nums.length)//it's true
              //we have other permutation [1,3,2]
              finish this level of recursion, return to last level
          i = 3 then end and delete '2' number
      i = 3 then end and delete '3' number
   now i = 2 // see this is the first recursion and templist = []
   add to temp list nums[1] = 2
   call backtracking
      backtracking([],[2,],[1,2,3]) // and you can continues the recursion.

I recommend use debug in netbeans or eclipse, You can see each level of recursion and see how it works.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.