## Wednesday, May 4, 2022

### Question 32 : Permutations of array in java.

Given array of distinct integers, print all permutations of the array.

For example :

``````array : [10, 20, 30]

Permuations are :

[10, 20, 30]
[10, 30, 20]
[20, 10, 30]
[20, 30, 10]
[30, 10, 20]
[30, 20, 10]``````

We can solve the problem with the help of recursion. It is quite hard to explain recursion, so I have created a recursion tree to demonstrate it.

Here is the code for the same.

``````import java.util.ArrayList;
import java.util.List;

public class PermutateArray {

public static void main(String[] args) {
PermutateArray pa=new PermutateArray();

int[] arr= {10, 20, 30};

List<List<Integer>> permute = pa.permute(arr);

System.out.println("Permuations of array : [10, 20, 30] are:");
System.out.println("=========================================");
for(List<Integer> perm:permute)
{
System.out.println(perm);
}

}
public List<List<Integer>> permute(int[] arr) {
List<List<Integer>> list = new ArrayList<>();
permuteHelper(list, new ArrayList<>(), arr);
return list;
}

private void permuteHelper(List<List<Integer>> list, List<Integer> resultList, int [] arr){

// Base case
if(resultList.size() == arr.length){
list.add(new ArrayList<>(resultList));
}
else{
for(int i = 0; i < arr.length; i++){

if(resultList.contains(arr[i]))
{
// If element already exists in the list then skip
continue;
}
// Choose element
resultList.add(arr[i]);
// Explore
permuteHelper(list, resultList, arr);
// Unchoose element
resultList.remove(resultList.size() - 1);
}
}
} ``````

When you run above program, you will get below output:

``````Permuations of array : [10, 20, 30] are:
=========================================
[10, 20, 30] [10, 30, 20] [20, 10, 30] [20, 30, 10] [30, 10, 20] [30, 20, 10]``````

have illustrated how recursion is working here with below diagram.

## Problem 2

Given array of integers(can contain duplicates), print all permutations of the array.

## Solution

We can solve this using recursion as well but need to take care of duplicates.We will sort the array, so all duplicates will be conitguous.

``````import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class PermuteArrayWithDuplicates {

public static void main(String[] args) {
PermuteArrayWithDuplicates pa=new PermuteArrayWithDuplicates();

int[] arr= {10, 20, 10};

List<List<Integer>> permute = pa.permute(arr);

System.out.println("Permuations of array : [10, 20, 10] are:");
System.out.println("=========================================");
for(List<Integer> perm:permute)
{
System.out.println(perm);
}

}
public List<List<Integer>> permute(int[] arr) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(arr);
permuteHelper(list, new ArrayList<>(), arr,new boolean[arr.length]);
return list;
}

private void permuteHelper(List<List<Integer>> list, List<Integer> resultList, int [] arr, boolean [] used){

// Base case
if(resultList.size() == arr.length){
list.add(new ArrayList<>(resultList));
} else{
for(int i = 0; i < arr.length; i++){
if(used[i] || i > 0 && arr[i] == arr[i-1] && !used[i - 1])
{
// If element is already used
continue;
}
// choose element
used[i] = true;
resultList.add(arr[i]);

// Explore
permuteHelper(list, resultList, arr, used);

// Unchoose element
used[i] = false;
resultList.remove(resultList.size() - 1);
}
}
}

}``````
``````Permuations of array : [10, 20, 10] are:
=========================================
[10, 10, 20] [10, 20, 10] [20, 10, 10]``````

Don't miss the next article!
Be the first to be notified when a new article or Kubernetes experiment is published.

Share This

## You may also like

Kubernetes Microservices
Python AI/ML
Spring Framework Spring Boot
Core Java Java Coding Question
Maven AWS