# Leetcode Permutations  Difficulty Level Medium
algorithms Backtracking coding Interview interviewprep LeetCode LeetCodeSolutions

In this leetcode problem premutation we have given an array of distinct integers, print all of its possible permutations.

## Examples  Input
arr[] = {1, 2, 3}
Output
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Input
arr[] = {1, 2, 3, 4}
Output
1 2 3 4
1 2 4 3
2 1 3 4
2 1 4 3
1 3 2 4
1 3 4 2
2 3 1 4
2 3 4 1
1 4 3 2
1 4 2 3
2 4 3 1
2 4 1 3
3 2 1 4
3 2 4 1
4 2 3 1
4 2 1 3
3 1 2 4
3 1 4 2
4 3 2 1
4 3 1 2
3 4 1 2
3 4 2 1
4 1 3 2
4 1 2 3

## Algorithm for Leetcode problem Permutations  All the permutations can be generated using backtracking.

1. To generate all the permutations of an array from index l to r, fix an element at index l and recur for the index l+1 to r.
2. Backtrack and fix another element at index l and recur for index l+1 to r.
3. Repeat the above steps to generate all the permutations.

## Explanation for Leetcode problem Permutations  Consider the example arr[] = {1, 2, 3}

Fix an element in the first position, we have three choices 1, or 2, or 3. The image below the second level represents this situation. In the first column of second-level 1 is fixed at the first position, in the second column 2 is fixed at the first position and in the third column 3 is fixed at the first position. After fixing an element at the first position, fix an element at the second position, consider the case in the second level and the first column, that is, {1, 2, 3}, 1 is fixed at the first position, so we have 2 choices for the second position that is either 2 or 3. Fixing the second position automatically fixes the third position. See the image above for clarification.

Wiggle Sort

Do this for all the cases and it will generate all possible permutations of the given array.

## JAVA Code  ```public class LeetcodePermutations {
// Function to generate all the permutations from l to r
private static void permute(int[] arr, int l, int r) {
if (l == r) {
// Print this permutation
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
return;
}
for (int i = l; i <= r; i++) {
// Fix an element at index l
swap(arr, l, i);
// Recur for index l + 1 to r
permute(arr, l + 1, r);
// Back track
swap(arr, l, i);
}
}

// Function to swap element at index x and y of array arr
private static void swap(int arr[], int x, int y) {
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}

public static void main(String[] args) {
// Example
int arr[] = new int[] {1, 2, 3};
int n = arr.length;
// Generate permutations from index 0 to n - 1
permute(arr, 0, n - 1);
}
}```

## C++ Code  ```#include<bits/stdc++.h>
using namespace std;

// Function to swap element at index x and y of array arr
void swap(int *arr, int x, int y) {
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}

// Function to generate all the permutations from l to r
void permute(int *arr, int l, int r, int n) {
if (l == r) {
// Print this permutation
for (int i = 0; i < n; i++) {
cout<<arr[i]<<" ";
}
cout<<endl;
return;
}
for (int i = l; i <= r; i++) {
// Fix an element at index l
swap(arr, l, i);
// Recur for index l + 1 to r
permute(arr, l + 1, r, n);
// Back track
swap(arr, l, i);
}
}

int main() {
// Example
int arr[] = {1, 2, 3};
int n = sizeof(arr) / sizeof(arr);
// Generate permutations from index 0 to n - 1
permute(arr, 0, n - 1, n);
return 0;
}```
```1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2```

## Complexity Analysis for Leetcode problem Permutations  Time Complexity = O(n!)
where n is the number of elements in the array.