
Introduction
Data Structures and Algorithms are the most elementary parts of a coding Interview. These are the favorites of the interviewers to be asked about. A mastery of Data Structures and Algorithms can help you in the long run.
Today, let’s learn about a famous and commonly asked Interview Problem, i.e., all the possible permutations of the distinct integers in a given array.
It is a famous and common problem that is solved using Dynamic Programming in its most optimized version.
Problem Statement:
Given an array nums of distinct integers, return all possible permutations in any order.
Examples:
Let the given array be [2, 3 ,5, 6]
All the possible permutations here are :
[3, 2, 5, 6] [3, 2, 6, 5] [3, 5, 2, 6] [3, 5, 6, 2] [3, 6, 5, 2] [3, 6, 2, 5] [2, 3, 5, 6] [2, 3, 6, 5]
[2, 5, 3, 6] [2, 5, 6, 3] [2, 6, 5, 3] [2, 6, 3, 5] [5, 2, 3, 6] [5, 2, 6, 3] [5, 3, 2, 6] [5, 3, 6, 2]
[5, 6, 3, 2] [5, 6, 2, 3] [6, 2, 5, 3] [6, 2, 3, 5] [6, 5, 2, 3] [6, 5, 3, 2] [6, 3, 5, 2] [6, 3, 2, 5]
Now, let's get started and learn various approaches to solve this problem.
Approach - Using Backtracking
We could find all the possible permutations of the distinct integers in a given array via simply:
- Swapping all the integers with the i-th index
- Calculating all the permutations for (i + 1)th index
- Backtracking or re-swapping i-th index with the previously swapped integer in (1).
Once, our i-th index reaches the last index of the array, this means all the swappings have been performed for that particular swap (of original 0th index with rest of the integers), and an answer has been generated. So, we store this answer which is in the form of ArrayList in our array of ArrayList and finally return it.
Note: This is our base case as well.
Implementation
Let’s have a look at its implementation in Java -
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
Scanner s = new Scanner(System.in);
System.out.println("Enter size of array ");
int n = s.nextInt();
int[] nums = new int[n];
System.out.println("Enter integers in array");
for (int i = 0; i < n; i++) {
nums[i] = s.nextInt();
}
List<List<Integer>> list = new ArrayList<>();
list = permute(nums);
System.out.println("Possible permutations are: ");
for (int i = 0; i < list.size(); i++){
System.out.println(list.get(i));
}
}
public static List<List<Integer>> permute(int[] nums) {
// Forming arraylist for storing a particular permutation
List<List<Integer>> arrLL = new ArrayList<>();
// Adding all nums in arrayList
ArrayList<Integer> arrtemp = new ArrayList<>();
for (int i : nums) {
arrtemp.add(i);
}
// Calling the function
permutations(arrtemp,0, arrLL);
return arrLL;
}
// Solving via Backtracking
public static void permutations(ArrayList<Integer> arrtemp, int idx, List<List<Integer>> arrLL){
// Base Case
if (idx == arrtemp.size()){
arrLL.add(new ArrayList<Integer> (arrtemp));
return;
}
// Swapping with right side of idx
for (int i = idx; i < arrtemp.size(); i++){
swap(arrtemp, i, idx);
permutations(arrtemp, idx + 1, arrLL);
swap(arrtemp, i, idx);
}
}
public static void swap(ArrayList<Integer> arrtemp, int i, int idx){
int temp = arrtemp.get(i);
arrtemp.set(i, arrtemp.get(idx));
arrtemp.set(idx, temp);
}
}
Output:
Enter size of array 4
Enter integers in array 3 2 5 6
Possible permutations are:
[3, 2, 5, 6]
[3, 2, 6, 5]
[3, 5, 2, 6]
[3, 5, 6, 2]
[3, 6, 5, 2]
[3, 6, 2, 5]
[2, 3, 5, 6]
[2, 3, 6, 5]
[2, 5, 3, 6]
[2, 5, 6, 3]
[2, 6, 5, 3]
[2, 6, 3, 5]
[5, 2, 3, 6]
[5, 2, 6, 3]
[5, 3, 2, 6]
[5, 3, 6, 2]
[5, 6, 3, 2]
[5, 6, 2, 3]
[6, 2, 5, 3]
[6, 2, 3, 5]
[6, 5, 2, 3]
[6, 5, 3, 2]
[6, 3, 5, 2]
[6, 3, 2, 5]
Time and Space Complexity
Time Complexity: The Time Complexity is O(N!) as there are N integers in the given array of integers and the number of permutations that exist are N!.
Note: Swapping takes O(1) time to swap integers in ArrayList in java.
Space Complexity: The Space Complexity is O(1) as no extra space is being used.
Also read: Permutation of string