Approach
To find all the permutations of an array, we will use the backtracking type of algorithm and save all possible permutations in the set data structure to remove the duplicates.
Algorithm
- Make a vector nums that will store the current permutation.
- Make a set of vectors and push the vector nums into it.
- At last, print the content of this set; this will give us all possible permutations of the given array without any duplicates.
Let's make permutations of array [1,2,4]. In this case, we will keep the first index, 1, fixed and then try to make the permutations of the remaining elements. We will get: {1 2 4}, {1 4 2}
Now, we have all the permutations by keeping the 1 fixed. Now we will keep the 2, fixed at the first position and try to make the permutations. We will get: {2 1 4}, {2 4 1}.
Similarly, keeping 4 at the first position, we will get: {4 1 2}, {4 2 1}.
So, finding the permutation of 1,2, and 4 was easy. Now we will keep the same logic and try to find the permutations of 1,2,3, and 4.
We will first keep 1 fixed. Therefore we have now only 2, 3, and 4.
So we will make the permutations of these numbers by keeping the 2 fixed, we will get: {1 2 3 4}, {1 2 4 3}
Now, we will fix 3 from 2, 3 and 4, we will get: {1 3 2 4}, {1 3 4 2}.
Again, keeping 4 fixed from 2,3 and 4, we will get : {1 4 2 3}, {1 4 3 2}.
Now, we have all the permutations when 1 is fixed. Similarly, we will keep other digits fixed at first and obtain the remaining permutations. You can now notice that we are breaking the larger array into the smaller one. After obtaining permutations of the smaller size array, we will replace any digit of this new array with the last digit fixed in the array and again make permutations of this array. For example, After making all the permutations of the numbers 3 and 4, i.e {3 4} and {4 3} and getting the numbers {1 2 3 4} and {1 2 4 3}, we replaced {2} with {3} (2 was the lastly fixed digit of the number ). Now, the last two digits of the number are {2} and {4}. Now, we made the permutation of these digits and will get {1 3 2 4} and {1 3 4 2}.
Similarly, after getting all the permutations of the last three digits of an array, we will replace the first index and get all the permutations of the last three indexes.
So logic should be clear by now, so let’s Code the above solution.
Implementation in Java
import java.util.*;
public class A {
static void permutations(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> nums, int l, int h) {
if (l == h) {
ArrayList<Integer> nums1 = new ArrayList<Integer>(nums);
res.add(nums1);
return;
}
for (int i = l; i <= h; i++) {
// Swapping
int left = nums.get(l);
nums.set(l, nums.get(i));
nums.set(i, left);
// Calling permutations for
// next greater value of l
permutations(res, nums, l + 1, h);
// Backtracking
left = nums.get(l);
nums.set(l, nums.get(i));
nums.set(i, left);
}
}
static ArrayList<ArrayList<Integer>> permute(ArrayList<Integer> nums) {
// Declaring result variable
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer> >();
int x = nums.size() - 1;
// Calling permutations for the first
// time by passing l
// as 0 and h = nums.size()-1
permutations(res, nums, 0, x);
return res;
}
public static void main(String[] args) {
ArrayList<Integer> nums = new ArrayList<Integer>();
nums.add(1);
nums.add(2);
nums.add(4);
ArrayList<ArrayList<Integer>> res = permute(nums);
Set<ArrayList<Integer>> hs = new HashSet<ArrayList<Integer>>();
for (int i=0;i<res.size();i++){
hs.add(res.get(i));
}
System.out.println("There are " + hs.size() + "possible permutations");
res.forEach(System.out::println);
}
}
You can also try this code with Online Java Compiler
Run Code
Implementation in Python
# Function to find the all possible permutations
def permutations(res,nums,l,h):
# Base case
# Add the vector to result and return
if l==h:
res.append(nums[:])
return
# Permutations made
for i in range(l,h+1):
nums[l],nums[i]=nums[i],nums[l]
# Calling permutations for
# next greater value of l
permutations(res,nums,l+1,h)
nums[l],nums[i]=nums[i],nums[l]
# Function to get the all possible permutations
def permute(nums):
res = []
x = len(nums)-1
# Calling permutations for the first
# time by passing l
# as 0 and h = nums.size()-1
permutations(res,nums,0,x)
return res
nums = [1,2,4]
res = permute(nums)
s = set()
for x in res:
s.add(tuple(x))
print("there are ",len(s),"possible permutations")
for x in s:
for y in x:
print(y,end=" ")
print()
You can also try this code with Online Python Compiler
Run Code
Implementation in C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function for swapping two numbers
void swap(int& x, int& y)
{
int temp = x;
x = y;
y = temp;
}
// Function to find the all possible permutations
void permutations(vector<vector<int> >& res,
vector<int> nums, int l, int h)
{
// Base case
// Add the vector to result and return
if (l == h) {
res.push_back(nums);
return;
}
// Permutations made
for (int i = l; i <= h; i++) {
// Swapping
swap(nums[l], nums[i]);
// Calling permutations for
// next greater value of l
permutations(res, nums, l + 1, h);
// Backtracking
swap(nums[l], nums[i]);
}
}
// Function to get the all possible permutations
vector<vector<int> > permute(vector<int>& nums)
{
// Declaring result variable
vector<vector<int> > res;
int x = nums.size() - 1;
// Calling permutations for the first
// time by passing l
// as 0 and h = nums.size()-1
permutations(res, nums, 0, x);
return res;
}
// Driver Code
int main()
{
vector<int> nums = { 1, 2, 4 };
vector<vector<int> > res = permute(nums);
// printing result
set<vector<int>>s;
for (auto x : res) {
s.insert(x);
}
cout << "There are " << s.size() << " possible permuatations" << endl;
for(auto x : s){
for(auto y : x)
cout << y << " ";
cout << endl;
}
return 0;
}
You can also try this code with Online C++ Compiler
Run Code
Output:
There are 6 possible permutations
1 2 4
1 4 2
2 1 4
2 4 1
4 1 2
4 2 1
Complexity Analysis
Time Complexity: O(N*N!)
Explanation: N is the time for printing all possible permutations and there are total N! Possible permutations.
Space Complexity: O(N)
Check out this problem - Pair Sum In Array.
Frequently Asked Questions
What is the difference between backtracking and recursion?
In recursion, we use the function calls themselves until it reaches a base case, while in case of backtracking, we use recursion to explore all the possibilities until we get the best result for the problem.
How many permutations if there are some identical elements?
Repetitions in the array are taken care of by dividing the permutation by the factorial of the number of identical objects.
What is the sum of all possible combinations of a given array of size n?
The sum of all possible combinations of n distinct things is 2 n.
C0 + nC1 + nC2 + . . . + nC n = 2 n.
Conclusion
This article discussed the problem of printing all possible permutations of an array without duplicates. We hope you understand the problem and solution properly. Now you can try the more similar questions on Binary Search Tree.
Some problems are suggested for you on the permutations topic
If you are a beginner, interested in coding, and want to learn Data Structure and Algorithms, check out our courses, Top Array Coding Interview Questions and problems, available on Coding Ninjas Studio, which is free!
Moreover, you can visit different sets of problems on Backtracking and Recursion available on Coding Ninjas Studio, to ace the interviews of reputed product-based companies like Amazon, Microsoft, Google, and more. Attempt our mock test series and participate in the contests hosted on Coding Ninjas Studio now! Also, look at the interview experiences and interview bundle for placement preparations.
On the other hand, learning never ceases, and there is always more to learn. So, keep learning and keep growing, ninjas!
Good luck with your preparation!