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):
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:
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:
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:
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:
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:
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
