how to understand this recursion in the leecode?

user_16710993 0
Viewed 73

new to java,I read the answer in the leecode ,and it ask for a array like [1,2,3]and return its permutation [1,3,2],[2,1,3].....and feel confused especially this code

Collections.swap(output, first, i);
backtrack(n, output, res, first + 1);

I do not know why the use Collections.swap(output,first,i) I think in first loop ,the first and i is equal to 0,so why use swap here. they are same vaule. what this recursion actually do,I debug it and can not figure out.code is below:

package com.company;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

 class Main {

public static void main(String[] args) {
    int[]arr=new int[]{1,2,3};
    Main main1=new Main();
    List<List<Integer>> lists = main1.permute(arr);
    System.out.println(lists);

}

   public List<List<Integer>> permute(int[] nums) {
       List<List<Integer>> res = new ArrayList<List<Integer>>();

       List<Integer> output = new ArrayList<Integer>();
       for (int num : nums) {
           output.add(num);
       }

       int n = nums.length;
       backtrack(n, output, res, 0);
       return res;
   }

   public void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) {
       
       if (first == n) {
           res.add(new ArrayList<Integer>(output));
       }
       for (int i = first; i < n; i++) {
           
           Collections.swap(output, first, i);
          
           backtrack(n, output, res, first + 1);
          
           Collections.swap(output, first, i);
       }
   }
}
recursion algorithm java
2 Answers

According to the documentation, the swap() method of java.util.Collections class is used to swap the elements at the specified positions in the specified list. If the specified positions are equal, invoking this method leaves the list unchanged.

So in a recursive technique, it is ok to have that call even though it does nothing in that particular condition, just to make the logic easier to implement and understand. If you want to avoid that, you will un-necessarily need to bring conditional statements into the logic, which is really not required.

user_4493780

Here is a somewhat simplified and commented version that may help follow what the code does:

import java.util.*;

public class Main   {

    public static void main(String[] args) {
        int[]arr=new int[]{1,2,3};
        List<List<Integer>> permutations = new Main().permute(arr);
        System.out.println(permutations);
    }

       public List<List<Integer>> permute(int[] nums) {

           List<List<Integer>> result = new ArrayList<>();
           List<Integer> input = new ArrayList<>();
           for (int num : nums) {
               input.add(num);
           }

           backtrack(input, result, 0);
           return result;
       }

       public void backtrack(List<Integer> input, List<List<Integer>> result, int currentIndex) {

           if (currentIndex == input.size() ) { //index passed the end of the collection
               result.add(new ArrayList<>(input)); //add the permutation to the returned result
               //the method return here because when currentIndex == input.size()
               //next for loop will not be executed
               //you may add a return here. It may improve the readability of the code
           }

           //iterate over each element of the array form currentIndex to the end
           for (int i = currentIndex; i < input.size(); i++) {

               Collections.swap(input, currentIndex, i);//create a permutation by swapping

               backtrack(input, result, currentIndex + 1); //increment currentIndex and process new permutation

               Collections.swap(input, currentIndex, i);//undo permutation before next loop
           }
       }
}
user_39929390
Related