Permutations of given String

Last Updated : 26 Mar, 2026

Given a string s, return all permutations of the string s in lexicographically sorted order.

Note: A permutation is the rearrangement of all the elements of a string.

Examples:

Input: s = "ABC"
Output: "ABC", "ACB", "BAC", "BCA", "CAB", "CBA"

Input: s = "XY"
Output: "XY", "YX"

Input: s = "AAA"
Output: "AAA", "AAA", "AAA", "AAA", "AAA", "AAA"

Try it on GfG Practice
redirect icon

[Approach] Recursion and Swapping - O(n! * n) Time

Generate permutations by fixing one position at a time. First, we fix the first position and try every character in that position, then recursively generate all permutations for the remaining positions. After we fix the first position, we recursive repeat the process for the remaining string. Once we generate all permutations beginning with the current character, to bring the next character at its position in current string, we swap the next character, with the current character.

4
C++ 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Generate permutations using swapping
void recurPermute(int index, string &s, vector<string> &res) {
    if (index == s.size()) {
        res.push_back(s);   
        return;
    }

    for (int i = index; i < s.size(); i++) {
        swap(s[index], s[i]);

        // fix current position and recurse
        recurPermute(index + 1, s, res);

        // backtrack
        swap(s[index], s[i]);
    }
}

vector<string> findPermutation(string &s) {
    vector<string> res;

    recurPermute(0, s, res);

    // sort lexicographically
    sort(res.begin(), res.end());

    return res;
}

int main() {
    string s = "AAB";

    vector<string> res = findPermutation(s);

    for (auto x : res) cout << x << " ";

    return 0;
}
Java 
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class GFG {

    static void recurPermute(int index, char[] s, List<String> res) {
        if (index == s.length) {
            res.add(new String(s)); 
            return;
        }

        for (int i = index; i < s.length; i++) {
            // swap
            char temp = s[index];
            s[index] = s[i];
            s[i] = temp;

            recurPermute(index + 1, s, res);

            // backtrack
            temp = s[index];
            s[index] = s[i];
            s[i] = temp;
        }
    }

    static List<String> findPermutation(String s) {
        List<String> res = new ArrayList<>();

        recurPermute(0, s.toCharArray(), res);

        Collections.sort(res); 
        return res;
    }

    public static void main(String[] args) {
        String s = "AAB";
        List<String> res = findPermutation(s);

        for (String x : res) {
            System.out.print(x + " ");
        }
    }
}
Python 
def recurPermute(index, s, res):
    if index == len(s):
        res.append("".join(s)) 
        return

    for i in range(index, len(s)):
        # swap
        s[index], s[i] = s[i], s[index]

        recurPermute(index + 1, s, res)

        # backtrack
        s[index], s[i] = s[i], s[index]


def findPermutation(s):
    res = []
    s = list(s)

    recurPermute(0, s, res)

    res.sort()  
    return res


if __name__ == "__main__":
    s = "AAB"
    res = findPermutation(s)

    for x in res:
        print(x, end=" ")
C# 
using System;
using System.Collections.Generic;

class GFG {

    static void RecurPermute(int index, char[] s, List<string> res) {
        if (index == s.Length) {
            res.Add(new string(s)); 
            return;
        }

        for (int i = index; i < s.Length; i++) {
            // swap
            char temp = s[index];
            s[index] = s[i];
            s[i] = temp;

            RecurPermute(index + 1, s, res);

            // backtrack
            temp = s[index];
            s[index] = s[i];
            s[i] = temp;
        }
    }

    static List<string> FindPermutation(string s) {
        List<string> res = new List<string>();

        RecurPermute(0, s.ToCharArray(), res);

        res.Sort(); 
        return res;
    }

    static void Main() {
        string s = "AAB";
        var res = FindPermutation(s);

        foreach (var x in res) {
            Console.Write(x + " ");
        }
    }
}
JavaScript 
function recurPermute(index, s, res) {
    if (index === s.length) {
        res.push(s.join("")); 
        return;
    }

    for (let i = index; i < s.length; i++) {
        // swap
        [s[index], s[i]] = [s[i], s[index]];

        recurPermute(index + 1, s, res);

        // backtrack
        [s[index], s[i]] = [s[i], s[index]];
    }
}

function findPermutation(s) {
    let res = [];
    let arr = s.split("");

    recurPermute(0, arr, res);

    res.sort(); 
    return res;
}

// Driver code
let s = "AAB";
let res = findPermutation(s);

for (let x of res) {
    process.stdout.write(x + " ");
}

Output
AAB AAB ABA ABA BAA BAA

Related articles:

Comment

Explore