Table of contents
1.
Introduction
2.
Approach - Using Backtracking
2.1.
Implementation
2.2.
Time and Space Complexity
3.
Frequently Asked Questions
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

Author Raksha Jain
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?
DSA Problems

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) {
            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);
    }

}
You can also try this code with Online Java Compiler
Run Code

 

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

Frequently Asked Questions

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:


Recommended Readings:


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!

Live masterclass