# Permutations

## Introduction-

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 dp 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 to 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 -

Output:

## Time and Space Complexity-

Time Complexity: 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: O(1) as no extra space is being used.

1. What is a permutation?

Ans. 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.

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

Ans.  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 of time. So, it is a systematic way of trying out different sequences of decisions until we find one that "works."

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

Ans. 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)!

## Key Takeaways-

In this blog, we learned various approaches to find 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!.

Check out more blogs on different dp problems like LCS, Friends Pairing Problem to read more about these topics in detail. And if you liked this blog, share it with your friends!

Practice a variety of on CodeStudio  platform where you can find questions asked in all big-tech giants. 