Leetcode Permutations - Print all permutations of a given array

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

Table of Contents

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.

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.
Backtrack and fix another element at index l and recur for index l+1 to r.
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.

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[0]);
    // Generate permutations from index 0 to n - 1
    permute(arr, 0, n - 1, n);
    return 0;
}

Complexity Analysis for Leetcode problem Permutations

Time Complexity = O(n!)
where n is the number of elements in the array.

References