Java Program to Find All Permutations of a String

Use a recursive Java method like permute(String str, int l, int r) that swaps characters and calls itself to generate all permutations of the string.

Examples

Inputabc

Outputabc acb bac bca cab cba

Inputab

Outputab ba

Inputa

Outputa

How to Think About It

To find all permutations of a string, think of fixing one character at a time and recursively permuting the remaining characters. Swap the fixed character with each character in turn to explore all possible orders.

Algorithm

1

Get the input string and define start and end indices.

2

If start index equals end index, print the current string as one permutation.

3

Otherwise, loop from start to end index:

4

Swap the character at start with the character at current loop index.

5

Recursively call the function with start index increased by one.

6

Swap back the characters to restore original string before next iteration.

Code

java

public class Permutations {
    public static void permute(String str, int l, int r) {
        if (l == r) {
            System.out.print(str + " ");
        } else {
            for (int i = l; i <= r; i++) {
                str = swap(str, l, i);
                permute(str, l + 1, r);
                str = swap(str, l, i); // backtrack
            }
        }
    }

    public static String swap(String str, int i, int j) {
        char[] charArray = str.toCharArray();
        char temp = charArray[i];
        charArray[i] = charArray[j];
        charArray[j] = temp;
        return String.valueOf(charArray);
    }

    public static void main(String[] args) {
        String s = "abc";
        permute(s, 0, s.length() - 1);
    }
}

Output

abc acb bac bca cab cba 

Dry Run

Let's trace the input "abc" through the code to see how permutations are generated.

1

Initial call

permute("abc", 0, 2) - start=0, end=2

2

First loop i=0

Swap indices 0 and 0: "abc"; call permute("abc", 1, 2)

3

Second level loop i=1

Swap indices 1 and 1: "abc"; call permute("abc", 2, 2)

4

Base case reached

Print "abc"

5

Backtrack and second level loop i=2

Swap indices 1 and 2: "acb"; call permute("acb", 2, 2)

6

Base case reached

Print "acb"

7

Backtrack to first level loop i=1

Swap indices 0 and 1: "bac"; call permute("bac", 1, 2)

8

Second level loop i=1

Swap indices 1 and 1: "bac"; call permute("bac", 2, 2)

9

Base case reached

Print "bac"

10

Backtrack and second level loop i=2

Swap indices 1 and 2: "bca"; call permute("bca", 2, 2)

11

Base case reached

Print "bca"

12

Backtrack to first level loop i=2

Swap indices 0 and 2: "cba"; call permute("cba", 1, 2)

13

Second level loop i=1

Swap indices 1 and 1: "cba"; call permute("cba", 2, 2)

14

Base case reached

Print "cba"

15

Backtrack and second level loop i=2

Swap indices 1 and 2: "cab"; call permute("cab", 2, 2)

16

Base case reached

Print "cab"

Call	String	Action
permute("abc",0,2)	abc	Swap(0,0), recurse
permute("abc",1,2)	abc	Swap(1,1), recurse
permute("abc",2,2)	abc	Print permutation
permute("abc",1,2)	abc	Swap(1,2), recurse
permute("acb",2,2)	acb	Print permutation
permute("abc",0,2)	abc	Swap(0,1), recurse
permute("bac",1,2)	bac	Swap(1,1), recurse
permute("bac",2,2)	bac	Print permutation
permute("bac",1,2)	bac	Swap(1,2), recurse
permute("bca",2,2)	bca	Print permutation
permute("abc",0,2)	abc	Swap(0,2), recurse
permute("cba",1,2)	cba	Swap(1,1), recurse
permute("cba",2,2)	cba	Print permutation
permute("cba",1,2)	cba	Swap(1,2), recurse
permute("cab",2,2)	cab	Print permutation

Why This Works

Step 1: Recursive swapping

The code swaps characters to fix one character at a time and recursively permutes the rest, exploring all possible orders.

Step 2: Base case prints permutation

When the start index equals the end index, the current string is a complete permutation and is printed.

Step 3: Backtracking restores string

After recursive calls, swapping back restores the string to its original state to try other permutations.

Alternative Approaches

Using a character array and swapping in place

java

public class Permutations {
    public static void permute(char[] arr, int l, int r) {
        if (l == r) {
            System.out.print(new String(arr) + " ");
        } else {
            for (int i = l; i <= r; i++) {
                swap(arr, l, i);
                permute(arr, l + 1, r);
                swap(arr, l, i); // backtrack
            }
        }
    }

    public static void swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        String s = "abc";
        permute(s.toCharArray(), 0, s.length() - 1);
    }
}

This approach is more efficient because it avoids creating new strings on each swap.

Using backtracking with a boolean visited array

java

import java.util.*;
public class Permutations {
    public static void permute(String str) {
        List<Character> path = new ArrayList<>();
        boolean[] used = new boolean[str.length()];
        backtrack(str, path, used);
    }

    private static void backtrack(String str, List<Character> path, boolean[] used) {
        if (path.size() == str.length()) {
            for (char c : path) System.out.print(c);
            System.out.print(" ");
            return;
        }
        for (int i = 0; i < str.length(); i++) {
            if (used[i]) continue;
            used[i] = true;
            path.add(str.charAt(i));
            backtrack(str, path, used);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }

    public static void main(String[] args) {
        permute("abc");
    }
}

This method builds permutations by choosing unused characters, useful when input has duplicates.

Complexity: O(n!) time, O(n) space

Time Complexity

Generating all permutations requires factorial time O(n!) because there are n! permutations for a string of length n.

Space Complexity

The recursion stack and temporary storage use O(n) space, where n is the string length.

Which Approach is Fastest?

Swapping characters in a char array is faster than creating new strings each time, reducing overhead.

Approach	Time	Space	Best For
String swapping with new strings	O(n!)	O(n)	Simple code, less efficient
In-place char array swapping	O(n!)	O(n)	Better performance, less memory
Backtracking with visited array	O(n!)	O(n)	Handles duplicates well