Generate All Permutations of Array in DSA Java

Mental Model

We want to list every possible order of the items in the array by swapping elements step by step.

Analogy: Imagine you have 3 different colored balls and want to see all ways to line them up on a shelf. You try placing each ball first, then arrange the rest in every way possible.

[1, 2, 3]
 ↑
We start by fixing the first element and permuting the rest.

Dry Run Walkthrough

Input: array: [1, 2, 3]

Goal: Generate all possible orders of the array elements

Step 1: Fix element 1 at index 0, permute rest [2,3]

[1, 2, 3] ↑ at index 0

Why: Start with first element fixed to generate permutations of remaining

Step 2: Fix element 2 at index 1, permute rest [3]

[1, 2, 3] ↑ at index 1

Why: Fix second element to generate permutations of last element

Step 3: Add permutation [1, 2, 3] to results

[1, 2, 3]

Why: Reached last element, record current order

Step 4: Swap elements at index 1 and 2 to get [1, 3, 2]

[1, 3, 2] ↑ at index 1

Why: Change order to explore new permutation

Step 5: Add permutation [1, 3, 2] to results

[1, 3, 2]

Why: Reached last element, record current order

Step 6: Backtrack swap to restore [1, 2, 3]

[1, 2, 3] ↑ at index 0

Why: Restore original order to try next first element

Step 7: Swap elements at index 0 and 1 to get [2, 1, 3]

[2, 1, 3] ↑ at index 0

Why: Change first element to 2 and permute rest

Step 8: Fix element 1 at index 1, permute rest [3]

[2, 1, 3] ↑ at index 1

Why: Fix second element to generate permutations of last element

Step 9: Add permutation [2, 1, 3] to results

[2, 1, 3]

Why: Reached last element, record current order

Step 10: Swap elements at index 1 and 2 to get [2, 3, 1]

[2, 3, 1] ↑ at index 1

Why: Change order to explore new permutation

Step 11: Add permutation [2, 3, 1] to results

[2, 3, 1]

Why: Reached last element, record current order

Step 12: Backtrack swap to restore [2, 1, 3]

[2, 1, 3] ↑ at index 0

Why: Restore original order to try next first element

Step 13: Swap elements at index 0 and 2 to get [3, 1, 2]

[3, 1, 2] ↑ at index 0

Why: Change first element to 3 and permute rest

Step 14: Fix element 1 at index 1, permute rest [2]

[3, 1, 2] ↑ at index 1

Why: Fix second element to generate permutations of last element

Step 15: Add permutation [3, 1, 2] to results

[3, 1, 2]

Why: Reached last element, record current order

Step 16: Swap elements at index 1 and 2 to get [3, 2, 1]

[3, 2, 1] ↑ at index 1

Why: Change order to explore new permutation

Step 17: Add permutation [3, 2, 1] to results

[3, 2, 1]

Why: Reached last element, record current order

Step 18: Backtrack swap to restore [3, 1, 2]

[3, 1, 2]

Why: Restore original order after exploring all permutations

Result:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

Annotated Code

DSA Java

import java.util.*;

public class Permutations {

    public static void generatePermutations(int[] arr, int start, List<List<Integer>> result) {
        if (start == arr.length) {
            List<Integer> permutation = new ArrayList<>();
            for (int num : arr) permutation.add(num);
            result.add(permutation); // record current order
            return;
        }
        for (int i = start; i < arr.length; i++) {
            swap(arr, start, i); // swap to fix element at start
            generatePermutations(arr, start + 1, result); // permute rest
            swap(arr, start, i); // backtrack to restore order
        }
    }

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

    public static void main(String[] args) {
        int[] input = {1, 2, 3};
        List<List<Integer>> result = new ArrayList<>();
        generatePermutations(input, 0, result);
        for (List<Integer> perm : result) {
            System.out.println(perm);
        }
    }
}

if (start == arr.length - 1) {

Check if fixed all elements except last to record permutation

result.add(permutation); // record current order

Add current permutation to results

for (int i = start; i < arr.length; i++) {

Loop to swap each element into current start position

swap(arr, start, i); // swap to fix element at start

Fix element at start by swapping

generatePermutations(arr, start + 1, result); // permute rest

Recursively generate permutations of remaining elements

swap(arr, start, i); // backtrack to restore order

Backtrack swap to restore original array order

Output

[1, 2, 3]

[1, 3, 2]

[2, 1, 3]

[2, 3, 1]

[3, 1, 2]

[3, 2, 1]

Complexity Analysis

Time: O(n! * n) because there are n! permutations and copying each permutation of length n

Space: O(n! * n) to store all permutations and O(n) recursion stack for calls

vs Alternative: This backtracking approach is more efficient than generating all permutations by repeated insertions which can be more complex and less direct

Edge Cases

empty array

returns a list with one empty permutation

DSA Java

if (start == arr.length) {

array with one element

returns a list with that single element as the only permutation

DSA Java

if (start == arr.length) {

array with duplicate elements

generates permutations including duplicates; no filtering

DSA Java

for (int i = start; i < arr.length; i++) {

When to Use This Pattern

When asked to list all possible orders or arrangements of items, use backtracking with swapping to generate permutations efficiently.

Common Mistakes

Mistake: Not swapping back after recursive call causing wrong permutations
Fix: Add a swap to backtrack and restore original order after recursion

Mistake: Stopping recursion too early before fixing all elements
Fix: Ensure base case is when start reaches length of array to record full permutation

Summary

Generates every possible order of array elements by swapping and backtracking.

Use when you need to find all permutations of a list or array.

Fix one element at a time and permute the rest, then backtrack to try new orders.

Practice

1. What does generating all permutations of an array mean?

easy

A. Sorting the array in ascending order

B. Listing all possible orders of the array elements

C. Finding the largest element in the array

D. Removing duplicate elements from the array

Solution

1. Step 1: Understand permutations

   Permutations are all possible ways to arrange elements in order.

2. Step 2: Apply to array

   Generating all permutations means listing every possible order of the array elements.

3. Final Answer:

   Listing all possible orders of the array elements -> Option B

4. Quick Check:

   Permutations = all orders [OK]

Hint: Permutations = all ways to arrange elements [OK]

Common Mistakes:

• Confusing permutations with sorting
• Thinking permutations remove duplicates
• Mixing permutations with finding max element

2. Which Java method signature correctly defines a function to generate permutations of an integer array?

easy

A. public void generatePermutations(int[] arr, int start)

B. void generatePermutations(int arr[], int start) public

C. public int generatePermutations(int[] arr, int start)

D. public static generatePermutations(int[] arr, int start)

Solution

1. Step 1: Check method signature syntax

   In Java, method signature starts with access modifier, return type, method name, and parameters.

2. Step 2: Validate options

   public void generatePermutations(int[] arr, int start) correctly uses 'public void' and parameter types. void generatePermutations(int arr[], int start) public has wrong order. public int generatePermutations(int[] arr, int start) returns int but should be void. public static generatePermutations(int[] arr, int start) misses return type.

3. Final Answer:

   public void generatePermutations(int[] arr, int start) -> Option A

4. Quick Check:

   Correct Java method syntax = public void generatePermutations(int[] arr, int start) [OK]

Hint: Java method = access + return type + name + params [OK]

Common Mistakes:

• Missing return type in method signature
• Incorrect order of access modifier and return type
• Wrong return type for void methods

3. What is the output of the following Java code snippet?

public class PermTest {
  public static void permute(int[] arr, int start) {
    if (start == arr.length - 1) {
      for (int num : arr) System.out.print(num + " ");
      System.out.println();
      return;
    }
    for (int i = start; i < arr.length; i++) {
      int temp = arr[start];
      arr[start] = arr[i];
      arr[i] = temp;
      permute(arr, start + 1);
      temp = arr[start];
      arr[start] = arr[i];
      arr[i] = temp;
    }
  }
  public static void main(String[] args) {
    int[] arr = {1, 2};
    permute(arr, 0);
  }
}

medium

A. 1 2 \n2 1 \n

B. 1 2 \n1 2 \n

C. 2 1 \n1 2 \n

D. No output

Solution

1. Step 1: Trace recursive calls for arr = {1, 2}

   Start with start=0, swap arr[0] with arr[0] (no change), recurse with start=1, print 1 2. Then swap back, swap arr[0] with arr[1], arr becomes {2,1}, recurse start=1, print 2 1.

2. Step 2: Confirm output lines

   Two lines printed: '1 2' and '2 1', each followed by newline.

3. Final Answer:

   1 2 \n2 1 \n -> Option A

4. Quick Check:

   All permutations of [1,2] = 1 2 and 2 1 [OK]

Hint: Swap and recurse to generate permutations [OK]

Common Mistakes:

• Forgetting to swap back after recursion
• Printing before reaching last index
• Confusing order of swaps

4. Identify the error in this Java method for generating permutations:

public void permute(int[] arr, int start) {
  if (start == arr.length) {
    System.out.println(Arrays.toString(arr));
    return;
  }
  for (int i = start; i < arr.length; i++) {
    int temp = arr[start];
    arr[start] = arr[i];
    arr[i] = temp;
    permute(arr, start + 1);
  }
}

medium

A. Using Arrays.toString incorrectly

B. Incorrect base case condition

C. Missing swap back after recursive call

D. Wrong loop range in for loop

Solution

1. Step 1: Analyze swapping logic

   After swapping arr[start] and arr[i], the method calls recursion but does not swap back, so array stays changed for next iterations.

2. Step 2: Identify missing swap back

   To restore original array before next iteration, swap back is needed after recursive call.

3. Final Answer:

   Missing swap back after recursive call -> Option C

4. Quick Check:

   Swap back needed to restore array [OK]

Hint: Always swap back after recursion to restore array [OK]

Common Mistakes:

• Not swapping back after recursion
• Incorrect base case index
• Misusing Arrays.toString for printing

5. You want to generate all permutations of an array with possible duplicate elements, but avoid printing duplicate permutations. Which approach is best?

hard

A. Use a HashSet to store and print only unique permutations after generating all

B. Only swap elements if they are different values

C. Generate all permutations without any checks and print all

D. Sort the array first and skip swapping duplicate elements during recursion

Solution

1. Step 1: Understand duplicates in permutations

   Duplicates cause repeated permutations if not handled. Sorting helps group duplicates together.

2. Step 2: Skip swapping duplicates during recursion

   By sorting and skipping swaps of same values at the same recursion level, duplicates are avoided efficiently.

3. Final Answer:

   Sort the array first and skip swapping duplicate elements during recursion -> Option D

4. Quick Check:

   Sort + skip duplicates = unique permutations [OK]

Hint: Sort array and skip duplicate swaps to avoid repeats [OK]

Common Mistakes:

• Generating all then filtering duplicates (inefficient)
• Not sorting before recursion
• Only swapping if values differ misses some permutations