Introduction

Permutation generation is a classic interview topic, but the real implementation details matter once you use it in production code or serious algorithm exercises. A good Java solution needs a correct backtracking invariant first, then sensible choices about duplicate handling, memory usage, and stopping conditions.

Start with a Correct Backtracking Baseline

The standard in-place swap algorithm is a strong starting point because it is compact and avoids creating a new array at every recursion level. The key invariant is simple: positions before start are already fixed, and positions from start onward are still available.

1import java.util.Arrays;
2
3public class Permutations {
4    public static void permute(int[] values, int start) {
5        if (start == values.length) {
6            System.out.println(Arrays.toString(values));
7            return;
8        }
9
10        for (int i = start; i < values.length; i++) {
11            swap(values, start, i);
12            permute(values, start + 1);
13            swap(values, start, i);
14        }
15    }
16
17    private static void swap(int[] values, int i, int j) {
18        int tmp = values[i];
19        values[i] = values[j];
20        values[j] = tmp;
21    }
22
23    public static void main(String[] args) {
24        permute(new int[] {1, 2, 3}, 0);
25    }
26}

The second swap call is not optional. It restores the array so the next branch starts from a clean state. If you forget that step, later permutations are built on corrupted data and the output quickly becomes wrong.

Handle Duplicate Input Explicitly

If the input can contain repeated values, the naive swap algorithm emits duplicate permutations. The usual fix is to track which values have already been placed at the current recursion depth.

1import java.util.Arrays;
2import java.util.HashSet;
3import java.util.Set;
4
5public class UniquePermutations {
6    public static void permuteUnique(int[] values, int start) {
7        if (start == values.length) {
8            System.out.println(Arrays.toString(values));
9            return;
10        }
11
12        Set<Integer> usedAtDepth = new HashSet<>();
13        for (int i = start; i < values.length; i++) {
14            if (!usedAtDepth.add(values[i])) {
15                continue;
16            }
17
18            swap(values, start, i);
19            permuteUnique(values, start + 1);
20            swap(values, start, i);
21        }
22    }
23
24    private static void swap(int[] values, int i, int j) {
25        int tmp = values[i];
26        values[i] = values[j];
27        values[j] = tmp;
28    }
29
30    public static void main(String[] args) {
31        permuteUnique(new int[] {1, 1, 2}, 0);
32    }
33}

This depth-local set is much cheaper than generating every permutation and removing duplicates later.

Decide Whether to Collect or Stream Results

For small inputs, returning a List<List<Integer>> is fine. For larger search spaces, collecting everything in memory is usually the wrong design because permutation counts grow factorially. Even 10! is already 3,628,800 permutations.

If you only need to inspect or validate permutations as they are produced, stream them to a visitor instead of storing them all:

1import java.util.Arrays;
2import java.util.function.Consumer;
3
4public class StreamingPermutations {
5    public static void permute(int[] values, int start, Consumer<int[]> consumer) {
6        if (start == values.length) {
7            consumer.accept(values.clone());
8            return;
9        }
10
11        for (int i = start; i < values.length; i++) {
12            swap(values, start, i);
13            permute(values, start + 1, consumer);
14            swap(values, start, i);
15        }
16    }
17
18    private static void swap(int[] values, int i, int j) {
19        int tmp = values[i];
20        values[i] = values[j];
21        values[j] = tmp;
22    }
23
24    public static void main(String[] args) {
25        permute(new int[] {1, 2, 3}, 0, p -> System.out.println(Arrays.toString(p)));
26    }
27}

Cloning before calling the consumer is important here because the source array is mutated after each callback.

Prune Early When the Problem Allows It

In real search problems, you often do not need every permutation. You may only care about permutations that satisfy a prefix condition, such as a partial sum limit or a forbidden adjacency rule. In those cases, pruning early usually gives more benefit than low-level micro-optimizations.

For example, if no valid solution can start with duplicate neighboring values, reject that branch immediately instead of waiting until the full permutation is built.

This is also where API design matters. A generator that can stop early is more useful than one that always materializes the full result set.

Consider Lexicographic Generation When Order Matters

Sometimes you need permutations in deterministic sorted order, or you want to resume from the current permutation. In those cases, the iterative nextPermutation algorithm can be a better fit than recursive backtracking.

1import java.util.Arrays;
2
3public class NextPermutationDemo {
4    static boolean nextPermutation(int[] values) {
5        int i = values.length - 2;
6        while (i >= 0 && values[i] >= values[i + 1]) {
7            i--;
8        }
9        if (i < 0) {
10            return false;
11        }
12
13        int j = values.length - 1;
14        while (values[j] <= values[i]) {
15            j--;
16        }
17
18        swap(values, i, j);
19        reverse(values, i + 1, values.length - 1);
20        return true;
21    }
22
23    static void swap(int[] values, int i, int j) {
24        int tmp = values[i];
25        values[i] = values[j];
26        values[j] = tmp;
27    }
28
29    static void reverse(int[] values, int left, int right) {
30        while (left < right) {
31            swap(values, left++, right--);
32        }
33    }
34
35    public static void main(String[] args) {
36        int[] values = {1, 2, 3};
37        do {
38            System.out.println(Arrays.toString(values));
39        } while (nextPermutation(values));
40    }
41}

This method only works as intended when you start from sorted input, but it is excellent when ordering guarantees matter.

Common Pitfalls

The classic bug is forgetting to swap values back after the recursive call. Another common issue is ignoring duplicate input and then wondering why the output contains repeated permutations. Developers also underestimate factorial growth and return giant lists from utility methods that should have been streaming or short-circuiting. Finally, callback-based designs sometimes forget to copy the current permutation before handing it to callers, which means the caller sees a mutated array later.

Summary

• Start with a simple in-place backtracking algorithm and get the state restoration right.
• Guard against duplicate values when the input is not guaranteed to be unique.
• Stream permutations instead of collecting them all when the search space is large.
• Add pruning logic when the target problem has prefix constraints.
• Use lexicographic generation if you need stable ordering or resume behavior.