Java Program to Find All Permutations of a String

Use a recursive method in Java that swaps characters to generate all permutations, like permute(char[] arr, int l, int r) which swaps characters and calls itself until all permutations are printed.

Examples

Input"abc"

Outputabc acb bac bca cab cba

Input"ab"

Outputab ba

Input"a"

Outputa

How to Think About It

To find all permutations of a string, think of fixing one character at a time and swapping it with every other character in the string. Then, recursively find permutations of the remaining characters. This way, you explore all possible orders by swapping and backtracking.

Algorithm

1

Convert the input string to a character array.

2

Create a recursive function that takes the array, a starting index, and an ending index.

3

If the starting index equals the ending index, print the current permutation.

4

Otherwise, loop from the starting index to the ending index:

5

Swap the current index with the loop index.

6

Recursively call the function with the next starting index.

7

Swap back to restore the original array (backtracking).

Code

java

public class Permutations {
    public static void permute(char[] arr, int l, int r) {
        if (l == r) {
            System.out.println(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
            }
        }
    }

    private 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 str = "abc";
        permute(str.toCharArray(), 0, str.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(['a','b','c'], 0, 2) - start at index 0

2

First loop iteration i=0

Swap arr[0] and arr[0]: ['a','b','c'] Call permute(['a','b','c'], 1, 2)

3

Second level first loop i=1

Swap arr[1] and arr[1]: ['a','b','c'] Call permute(['a','b','c'], 2, 2) Print 'abc'

4

Backtrack second level

Swap back arr[1] and arr[1]: ['a','b','c']

5

Second level second loop i=2

Swap arr[1] and arr[2]: ['a','c','b'] Call permute(['a','c','b'], 2, 2) Print 'acb'

6

Backtrack second level

Swap back arr[1] and arr[2]: ['a','b','c']

7

Backtrack first level

Swap back arr[0] and arr[0]: ['a','b','c']

8

First loop second iteration i=1

Swap arr[0] and arr[1]: ['b','a','c'] Call permute(['b','a','c'], 1, 2)

9

Second level first loop i=1

Swap arr[1] and arr[1]: ['b','a','c'] Call permute(['b','a','c'], 2, 2) Print 'bac'

10

Backtrack second level

Swap back arr[1] and arr[1]: ['b','a','c']

11

Second level second loop i=2

Swap arr[1] and arr[2]: ['b','c','a'] Call permute(['b','c','a'], 2, 2) Print 'bca'

12

Backtrack second level

Swap back arr[1] and arr[2]: ['b','a','c']

13

Backtrack first level

Swap back arr[0] and arr[1]: ['a','b','c']

14

First loop third iteration i=2

Swap arr[0] and arr[2]: ['c','b','a'] Call permute(['c','b','a'], 1, 2)

15

Second level first loop i=1

Swap arr[1] and arr[1]: ['c','b','a'] Call permute(['c','b','a'], 2, 2) Print 'cba'

16

Backtrack second level

Swap back arr[1] and arr[1]: ['c','b','a']

17

Second level second loop i=2

Swap arr[1] and arr[2]: ['c','a','b'] Call permute(['c','a','b'], 2, 2) Print 'cab'

18

Backtrack second level

Swap back arr[1] and arr[2]: ['c','b','a']

19

Backtrack first level

Swap back arr[0] and arr[2]: ['a','b','c']

Permutation Generated
abc
acb
bac
bca
cab
cba

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 orders.

Step 2: Backtracking

After recursive calls, it swaps back to restore the original order, allowing other permutations to be generated correctly.

Step 3: Base case

When the starting index reaches the end, the current arrangement is a complete permutation and is printed.

Alternative Approaches

Using a list to track used characters

java

import java.util.*;
public class PermutationsAlt {
    public static void permute(String prefix, String str) {
        if (str.length() == 0) {
            System.out.println(prefix);
        } else {
            for (int i = 0; i < str.length(); i++) {
                permute(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1));
            }
        }
    }
    public static void main(String[] args) {
        permute("", "abc");
    }
}

This method builds permutations by choosing each character and removing it from the remaining string, which is simpler but less efficient due to string concatenation.

Using Heap's Algorithm

java

public class HeapPermutations {
    public static void heapPermute(char[] arr, int n) {
        if (n == 1) {
            System.out.println(new String(arr));
            return;
        }
        for (int i = 0; i < n; i++) {
            heapPermute(arr, n - 1);
            if (n % 2 == 0) {
                swap(arr, i, n - 1);
            } else {
                swap(arr, 0, n - 1);
            }
        }
    }
    private 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) {
        char[] arr = "abc".toCharArray();
        heapPermute(arr, arr.length);
    }
}

Heap's algorithm generates permutations with minimal swaps and is efficient for larger inputs.

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

Time Complexity

Generating all permutations requires factorial time O(n!) because there are n! possible orders for n characters.

Space Complexity

The recursion stack uses O(n) space for the depth, and swapping is done in place, so no extra arrays are needed.

Which Approach is Fastest?

The swapping method with backtracking is generally faster and uses less memory than string concatenation methods; Heap's algorithm can be more efficient for large inputs.

Approach	Time	Space	Best For
Swapping with backtracking	O(n!)	O(n)	General use, efficient in-place
String concatenation recursion	O(n * n!)	O(n!)	Simple code, less efficient
Heap's algorithm	O(n!)	O(n)	Efficient swaps, large inputs