Permutations of a string or array

Given a string or an array of distinct characters, return all possible permutations.

Input-Output Examples

Example 1:

Input: s = "abc"
Output: ["abc", "acb", "bac", "bca", "cab", "cba"]

Example 2:

Input: nums = [1, 2, 3]
Output: [  [1, 2, 3],  [1, 3, 2],  [2, 1, 3],  [2, 3, 1],  [3, 1, 2],  [3, 2, 1]

Approach:
Technique: Backtracking

  1. Initialization: Create a list to store the permutations.
  2. Backtracking Function:
    • Use a recursive function to generate permutations by swapping elements.
    • Iterate through the elements, swapping the current element with the rest of the elements.
    • Recursively call the function for the next position.
    • Backtrack by swapping the elements back to their original positions.
  3. Return: Add the generated permutations to the list and return it.

C++ Program to print all the permutations of a string or array

cpp
#include <iostream>
#include <vector>
#include <string>
using namespace std;

// Function to generate permutations of a string
void permute(vector<string>& permutations, string s, int l, int r);
// Function to generate permutations of an array
void permuteArray(vector<vector<int>>& permutations, vector<int>& nums, int l, int r);

// Wrapper function to get permutations of a string
vector<string> getPermutations(string s) {
    vector<string> permutations;
    permute(permutations, s, 0, s.size() - 1);
    return permutations;
}

// Wrapper function to get permutations of an array
vector<vector<int>> getPermutations(vector<int>& nums) {
    vector<vector<int>> permutations;
    permuteArray(permutations, nums, 0, nums.size() - 1);
    return permutations;
}

// Function to generate permutations of a string using backtracking
void permute(vector<string>& permutations, string s, int l, int r) {
    if (l == r) {
        permutations.push_back(s);
    } else {
        for (int i = l; i <= r; i++) {
            swap(s[l], s[i]); // Swap characters
            permute(permutations, s, l + 1, r); // Recurse for the next position
            swap(s[l], s[i]); // Backtrack
        }
    }
}

// Function to generate permutations of an array using backtracking
void permuteArray(vector<vector<int>>& permutations, vector<int>& nums, int l, int r) {
    if (l == r) {
        permutations.push_back(nums);
    } else {
        for (int i = l; i <= r; i++) {
            swap(nums[l], nums[i]); // Swap elements
            permuteArray(permutations, nums, l + 1, r); // Recurse for the next position
            swap(nums[l], nums[i]); // Backtrack
        }
    }
}

int main() {
    string s = "abc";
    vector<string> stringPermutations = getPermutations(s);
    cout << "Permutations of string \"" << s << "\":" << endl;
    for (const string& perm : stringPermutations) {
        cout << perm << endl;
    }

    vector<int> nums = {1, 2, 3};
    vector<vector<int>> arrayPermutations = getPermutations(nums);
    cout << "Permutations of array [1, 2, 3]:" << endl;
    for (const vector<int>& perm : arrayPermutations) {
        for (int num : perm) {
            cout << num << " ";
        }
        cout << endl;
    }

    return 0;
}

Java Program to print all the permutations of a string or array

java
import java.util.*;

public class Permutations {
    public static void main(String[] args) {
        String s = "abc";
        List<String> stringPermutations = getPermutations(s);
        System.out.println("Permutations of string \"" + s + "\":");
        for (String perm : stringPermutations) {
            System.out.println(perm);
        }

        int[] nums = {1, 2, 3};
        List<List<Integer>> arrayPermutations = getPermutations(nums);
        System.out.println("Permutations of array [1, 2, 3]:");
        for (List<Integer> perm : arrayPermutations) {
            System.out.println(perm);
        }
    }

    // Wrapper function to get permutations of a string
    public static List<String> getPermutations(String s) {
        List<String> permutations = new ArrayList<>();
        permute(permutations, s.toCharArray(), 0, s.length() - 1);
        return permutations;
    }

    // Wrapper function to get permutations of an array
    public static List<List<Integer>> getPermutations(int[] nums) {
        List<List<Integer>> permutations = new ArrayList<>();
        permuteArray(permutations, nums, 0, nums.length - 1);
        return permutations;
    }

    // Function to generate permutations of a string using backtracking
    private static void permute(List<String> permutations, char[] s, int l, int r) {
        if (l == r) {
            permutations.add(new String(s));
        } else {
            for (int i = l; i <= r; i++) {
                swap(s, l, i); // Swap characters
                permute(permutations, s, l + 1, r); // Recurse for the next position
                swap(s, l, i); // Backtrack
            }
        }
    }

    // Function to generate permutations of an array using backtracking
    private static void permuteArray(List<List<Integer>> permutations, int[] nums, int l, int r) {
        if (l == r) {
            List<Integer> perm = new ArrayList<>();
            for (int num : nums) {
                perm.add(num);
            }
            permutations.add(perm);
        } else {
            for (int i = l; i <= r; i++) {
                swap(nums, l, i); // Swap elements
                permuteArray(permutations, nums, l + 1, r); // Recurse for the next position
                swap(nums, l, i); // Backtrack
            }
        }
    }

    // Utility function to swap two characters in a char array
    private static void swap(char[] s, int i, int j) {
        char temp = s[i];
        s[i] = s[j];
        s[j] = temp;
    }

    // Utility function to swap two elements in an int array
    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Python Program to print all the permutations of a string or array

python
from typing import List

def getPermutations(s: str) -> List[str]:
    permutations = []
    permute(permutations, list(s), 0, len(s) - 1)
    return permutations

def getPermutationsArray(nums: List[int]) -> List[List[int]]:
    permutations = []
    permuteArray(permutations, nums, 0, len(nums) - 1)
    return permutations

# Function to generate permutations of a string using backtracking
def permute(permutations: List[str], s: List[str], l: int, r: int) -> None:
    if l == r:
        permutations.append("".join(s))
    else:
        for i in range(l, r + 1):
            s[l], s[i] = s[i], s[l] # Swap characters
            permute(permutations, s, l + 1, r) # Recurse for the next position
            s[l], s[i] = s[i], s[l] # Backtrack

# Function to generate permutations of an array using backtracking
def permuteArray(permutations: List[List[int]], nums: List[int], l: int, r: int) -> None:
    if l == r:
        permutations.append(nums[:])
    else:
        for i in range(l, r + 1):
            nums[l], nums[i] = nums[i], nums[l] # Swap elements
            permuteArray(permutations, nums, l + 1, r) # Recurse for the next position
            nums[l], nums[i] = nums[i], nums[l] # Backtrack

if __name__ == "__main__":
    s = "abc"
    stringPermutations = getPermutations(s)
    print(f"Permutations of string \"{s}\":")
    for perm in stringPermutations:
        print(perm)

    nums = [1, 2, 3]
    arrayPermutations = getPermutationsArray(nums)
    print("Permutations of array [1, 2, 3]:")
    for perm in arrayPermutations:
        print(perm)

DSA

7073

293

Related Articles