Code: Find all Permutations of an array using Recursion | DSA in C++ - Software Development PDF Download

Here's a C++ code to find all permutations of an array using recursion:

#include <iostream>

#include <vector>

using namespace std;

void swap(vector<int>& arr, int i, int j) {

    int temp = arr[i];

    arr[i] = arr[j];

    arr[j] = temp;

}

void permutations(vector<int>& arr, int start, int end) {

    if (start == end) {

        // Base case: We have reached the end of the array

        // Print the current permutation

        for (int i = 0; i <= end; i++) {

            cout << arr[i] << " ";

        }

        cout << endl;

    } else {

        // Recursive case: Swap each element with the start element

        // and recursively generate permutations for the remaining elements

        for (int i = start; i <= end; i++) {

            swap(arr, start, i);

            permutations(arr, start + 1, end);

            swap(arr, start, i);  // Backtrack: Undo the swap

        }

    }

}

int main() {

    vector<int> arr = {1, 2, 3};

    int n = arr.size();

    cout << "Permutations of the array:" << endl;

    permutations(arr, 0, n - 1);

    return 0;

}

Output:

Permutations of the array:

1 2 3 

1 3 2 

2 1 3 

2 3 1 

3 2 1 

3 1 2

Explanation:

• The 'swap' function is used to swap two elements of the array given their indices.
• The 'permutations' function takes three parameters: the array 'arr', the starting index 'start', and the ending index 'end'.
• If 'start' and 'end' are equal, it means we have reached the end of the array, and we print the current permutation.
• Otherwise, we iterate over each element from 'start' to 'end', swap it with the element at 'start', and recursively generate permutations for the remaining elements by calling 'permutations' with 'start + 1' as the new starting index.
• After generating permutations for the remaining elements, we backtrack by swapping the elements back to their original positions. This ensures that the original array is unmodified when we move to the next iteration of the loop.
• In the 'main' function, we create an array 'arr' containing the elements {1, 2, 3}, and call 'permutations' with the initial values of 'start' as 0 and 'end' as 'n - 1', where 'n' is the size of the array.
• The program then prints all the permutations of the array.

The code utilizes recursion to generate permutations by systematically swapping elements and exploring all possible combinations. The base case ensures that the recursion stops when the end of the array is reached, and the permutations are printed. The recursive case generates permutations for the remaining elements by swapping the current element with each subsequent element and recursively generating permutations for the rest. Backtracking is performed to restore the array to its original state after each iteration.