1.
Introduction
2.
Approach - Using Backtracking
2.1.
Implementation
2.2.
Time and Space Complexity
3.
3.1.
What is a permutation?
3.2.
What is backtracking? How does it help in finding out our solution?
3.3.
What is the formula used to calculate the permutation of integers in mathematics?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Permutations

Raksha Jain
0 upvote

## 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:

1. Swapping all the integers with the i-th index
2. Calculating all the permutations for (i + 1)th index
3. 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) {
}

// 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()){
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.

### What is a permutation?

A permutation is a collection of objects from a set where the order or the arrangement of the chosen objects does matter. So, is an arrangement of objects in a definite order

### What is backtracking? How does it help in finding out our solution?

Backtracking is an algorithmic technique for solving problems recursively by building a solution incrementally - one piece at a time and removing those solutions that fail to satisfy the constraints of the problem at any point in time. So, it is a systematic way of trying out different sequences of decisions until we find one that "works."

### What is the formula used to calculate the permutation of integers in mathematics?

A permutation is the choice of ‘R’ things from a set of ‘N’ things without replacement and where the order matters. The formula used is: NPR = (N!) / (N-R)!

## Conclusion

In this blog, we learned various approaches to finding all the possible permutations of the distinct integers in a given array.

• A permutation is a collection of objects from a set where the order or the arrangement of the chosen objects does matter. So, is an arrangement of objects in a definite order
• A permutation is the choice of ‘R’ things from a set of ‘N’ things without replacement and where the order matters. In mathematics, the formula used is:

NPR = (N!) / (N-R)!

• The optimized time complexity of this problem is O(N!) as there are N integers in the given array of integers and the number of permutations that exist are N!.

Recommended Problems: