Java

array manipulation

permutation

character array

programming tutorial

Specific element permutation within an array of characters in JAVA?

Data Structures & Algorithms practice on Codemia

Step through 300+ coding interview problems with animated visualisers that show the data structure changing as the code runs. The Blind 75 are free.

Practice algorithms

Data Structures Math for Programmers Java

Introduction

To generate permutations of a character array in Java, use a recursive backtracking approach that swaps elements to explore all orderings. The base case prints or stores the permutation when the left index equals the right index. For arrays with duplicate characters, skip swaps where the same character would be placed at the same position to avoid duplicate permutations. The time complexity is O(n!) since there are n! permutations of n distinct elements.

Basic Recursive Permutation

The classic approach swaps each element into the current position, recurses on the remaining elements, then swaps back (backtracks):

java

1public class Permutations {
2    public static void permute(char[] arr, int left, int right) {
3        if (left == right) {
4            System.out.println(new String(arr));
5            return;
6        }
7
8        for (int i = left; i <= right; i++) {
9            swap(arr, left, i);           // Place arr[i] at position 'left'
10            permute(arr, left + 1, right); // Recurse on remaining positions
11            swap(arr, left, i);           // Backtrack — restore original order
12        }
13    }
14
15    private static void swap(char[] arr, int i, int j) {
16        char temp = arr[i];
17        arr[i] = arr[j];
18        arr[j] = temp;
19    }
20
21    public static void main(String[] args) {
22        char[] chars = {'A', 'B', 'C'};
23        permute(chars, 0, chars.length - 1);
24    }
25}

Output:

1ABC
2ACB
3BAC
4BCA
5CBA
6CAB

Collecting Permutations in a List

Instead of printing, store results for later use:

java

1import java.util.ArrayList;
2import java.util.List;
3
4public class PermutationCollector {
5    public static List<String> getPermutations(char[] arr) {
6        List<String> results = new ArrayList<>();
7        permute(arr, 0, arr.length - 1, results);
8        return results;
9    }
10
11    private static void permute(char[] arr, int left, int right, List<String> results) {
12        if (left == right) {
13            results.add(new String(arr));
14            return;
15        }
16
17        for (int i = left; i <= right; i++) {
18            swap(arr, left, i);
19            permute(arr, left + 1, right, results);
20            swap(arr, left, i);
21        }
22    }
23
24    private static void swap(char[] arr, int i, int j) {
25        char temp = arr[i];
26        arr[i] = arr[j];
27        arr[j] = temp;
28    }
29
30    public static void main(String[] args) {
31        List<String> perms = getPermutations(new char[]{'X', 'Y', 'Z'});
32        System.out.println("Count: " + perms.size()); // 6
33        perms.forEach(System.out::println);
34    }
35}

Handling Duplicate Characters

When the array contains duplicate characters (e.g., {'A', 'A', 'B'}), the basic algorithm generates duplicate permutations. Use a HashSet to skip duplicates:

java

1import java.util.*;
2
3public class UniquePermutations {
4    public static List<String> getUniquePermutations(char[] arr) {
5        List<String> results = new ArrayList<>();
6        permute(arr, 0, arr.length - 1, results);
7        return results;
8    }
9
10    private static void permute(char[] arr, int left, int right, List<String> results) {
11        if (left == right) {
12            results.add(new String(arr));
13            return;
14        }
15
16        Set<Character> used = new HashSet<>();
17        for (int i = left; i <= right; i++) {
18            // Skip if this character was already placed at position 'left'
19            if (used.contains(arr[i])) continue;
20            used.add(arr[i]);
21
22            swap(arr, left, i);
23            permute(arr, left + 1, right, results);
24            swap(arr, left, i);
25        }
26    }
27
28    private static void swap(char[] arr, int i, int j) {
29        char temp = arr[i];
30        arr[i] = arr[j];
31        arr[j] = temp;
32    }
33
34    public static void main(String[] args) {
35        List<String> perms = getUniquePermutations(new char[]{'A', 'A', 'B'});
36        System.out.println("Count: " + perms.size()); // 3 (not 6)
37        perms.forEach(System.out::println);
38        // AAB, ABA, BAA
39    }
40}

Permutations of Specific Elements Only

Permute only certain positions while keeping others fixed:

java

1public class PartialPermutation {
2    public static void permuteRange(char[] arr, int start, int end) {
3        permuteHelper(arr, start, end);
4    }
5
6    private static void permuteHelper(char[] arr, int left, int right) {
7        if (left == right) {
8            System.out.println(new String(arr));
9            return;
10        }
11
12        for (int i = left; i <= right; i++) {
13            swap(arr, left, i);
14            permuteHelper(arr, left + 1, right);
15            swap(arr, left, i);
16        }
17    }
18
19    private static void swap(char[] arr, int i, int j) {
20        char temp = arr[i];
21        arr[i] = arr[j];
22        arr[j] = temp;
23    }
24
25    public static void main(String[] args) {
26        char[] arr = {'A', 'B', 'C', 'D'};
27        // Only permute positions 1-2 (B, C), keep A and D fixed
28        permuteRange(arr, 1, 2);
29        // ABCD
30        // ACBD
31    }
32}

Iterative Approach (Next Permutation)

Generate permutations in lexicographic order without recursion:

java

1import java.util.Arrays;
2
3public class NextPermutation {
4    public static boolean nextPermutation(char[] arr) {
5        int n = arr.length;
6
7        // Find rightmost element smaller than its right neighbor
8        int i = n - 2;
9        while (i >= 0 && arr[i] >= arr[i + 1]) i--;
10
11        if (i < 0) return false; // Already the last permutation
12
13        // Find rightmost element greater than arr[i]
14        int j = n - 1;
15        while (arr[j] <= arr[i]) j--;
16
17        // Swap and reverse the suffix
18        swap(arr, i, j);
19        reverse(arr, i + 1, n - 1);
20        return true;
21    }
22
23    private static void reverse(char[] arr, int left, int right) {
24        while (left < right) {
25            swap(arr, left++, right--);
26        }
27    }
28
29    private static void swap(char[] arr, int i, int j) {
30        char temp = arr[i];
31        arr[i] = arr[j];
32        arr[j] = temp;
33    }
34
35    public static void main(String[] args) {
36        char[] arr = {'A', 'B', 'C'};
37        Arrays.sort(arr); // Start from smallest permutation
38
39        do {
40            System.out.println(new String(arr));
41        } while (nextPermutation(arr));
42        // ABC, ACB, BAC, BCA, CAB, CBA (lexicographic order)
43    }
44}

K-Permutations (Choose k from n)

Generate all permutations of k elements from an array of n:

java

1import java.util.ArrayList;
2import java.util.List;
3
4public class KPermutations {
5    public static List<String> permute(char[] arr, int k) {
6        List<String> results = new ArrayList<>();
7        permuteHelper(arr, 0, k, results);
8        return results;
9    }
10
11    private static void permuteHelper(char[] arr, int depth, int k, List<String> results) {
12        if (depth == k) {
13            results.add(new String(arr, 0, k));
14            return;
15        }
16
17        for (int i = depth; i < arr.length; i++) {
18            swap(arr, depth, i);
19            permuteHelper(arr, depth + 1, k, results);
20            swap(arr, depth, i);
21        }
22    }
23
24    private static void swap(char[] arr, int i, int j) {
25        char temp = arr[i];
26        arr[i] = arr[j];
27        arr[j] = temp;
28    }
29
30    public static void main(String[] args) {
31        List<String> perms = permute(new char[]{'A', 'B', 'C', 'D'}, 2);
32        System.out.println("2-permutations of ABCD: " + perms.size()); // 12
33        perms.forEach(System.out::println);
34        // AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC
35    }
36}

Common Pitfalls

Not backtracking after the recursive call: Forgetting to swap back after the recursive call corrupts the array for subsequent iterations. Always pair each swap(arr, left, i) with a matching swap(arr, left, i) after the recursion.
Generating duplicate permutations with repeated characters: The basic algorithm treats identical characters as distinct, producing duplicates like "AAB" twice. Use a HashSet to track which characters have already been placed at the current position.
Stack overflow on large arrays: The recursive approach uses O(n) stack depth. For arrays larger than ~10,000 elements (impractical for permutations due to O(n!) complexity), the JVM stack overflows. Use the iterative next-permutation approach for ordered traversal.
Confusing permutations with combinations: Permutations care about order (AB != BA), combinations do not (AB == BA). If order does not matter, use a combination algorithm instead, which produces fewer results.
Modifying the original array without copying: The swap-based approach modifies the input array in place. If you need the original array unchanged after generating permutations, pass a copy: permute(arr.clone(), 0, arr.length - 1).

Summary

Use recursive backtracking with swap to generate all permutations in O(n!) time
Skip duplicate characters with a HashSet at each recursion level to avoid duplicate permutations
Use the next-permutation algorithm for iterative, lexicographically ordered generation
For k-permutations (choose k from n), stop the recursion at depth k instead of depth n
Always backtrack (swap back) after the recursive call to restore the array state

System design interview problems on this topic

All system design practice problems

Course

Intermediate

27 lessons

15 hours

DSA Fundamentals

Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.

View the course

Data Structures & Algorithms practice on Codemia

Step through 300+ coding interview problems with animated visualisers that show the data structure changing as the code runs. The Blind 75 are free.

Practice algorithms

Specific element permutation within an array of characters in JAVA?

Data Structures & Algorithms practice on Codemia

Introduction

Basic Recursive Permutation

Collecting Permutations in a List

Handling Duplicate Characters

Permutations of Specific Elements Only

Iterative Approach (Next Permutation)

K-Permutations (Choose k from n)

Common Pitfalls

Summary

Related reading

System design interview problems on this topic

DSA Fundamentals

Data Structures & Algorithms practice on Codemia