Write a recursive method public static ArrayList permuteArra

Write a recursive method public static ArrayList permuteArray(int[] array) that returns an ArrayList of all permutations of the the parameter array. The ArrayList may contain the arrays in any order.

Suppose array = {4, 7, 1, 2}. Then the ArrayList would contain the following arrays, but in any order:

4 7 1 2

7 4 1 2

2 1 4 7

1 2 4 7

4 7 2 1

7 4 2 1

2 1 7 4

1 2 7 4

4 2 1 7

7 1 2 4

2 7 4 1

1 4 2 7

4 2 7 1

7 1 4 2

2 7 1 4

1 4 7 2

4 1 2 7

7 2 1 4

2 4 1 7

1 7 2 4

4 1 7 2

7 2 4 1

2 4 7 1

1 7 4 2

Note: You are permitted to use at most two loops in solving this problem. A set of doubly-nested for-loops would count as two loops for this purpose. Recursion must be used in some non-trivial way to help solve the problem. You may write helper methods if you like.

Solution

import java.util.ArrayList;
import java.util.Arrays;

public class PermutationArray {

   public static ArrayList permuteArray(int[] array) {
       ArrayList<String> list = new ArrayList<>();
       ArrayList<String> result = new ArrayList<>();
       if(array.length == 1) {
          
           list.add(String.valueOf(array[0]));
       } else {
           int[] tempArray= new int[array.length-1];
           int firstElement = array[0];
           System.arraycopy(array, 1, tempArray, 0, array.length-1);
           list = permuteArray(tempArray);
           for (String str:list) {
               for(int i=0; i<=str.length(); i++) {
                   String tempStr = str.substring(0, i)+firstElement+str.substring(i,str.length());
                   result.add(tempStr);
                   //System.out.println(\"str is \"+tempStr);
               }
           }
           return result;
          
       }

       return list;

   }

   public static void main(String[] args) {
       int[] arr={1,2,3,4,5};
       ArrayList aList = permuteArray(arr);
       System.out.println(Arrays.toString(aList.toArray()));
       System.out.println(\"Number of elements are \"+aList.size());
  
       System.out.println(\"From Main\");

   }
}