Generate All Permutations of Array in DSA Java - Execution Trace

Concept Flow - Generate All Permutations of Array

Start with full array

↓

Choose element at index i

↓

Swap element i with element j

↓

Recursively permute remaining elements

↓

Backtrack: swap back to restore array

↓

Repeat for next j

↓

All permutations generated

We pick each element in turn, swap it to the current position, recursively permute the rest, then swap back to restore the array for the next choice.

Execution Sample

DSA Java

void permute(int[] arr, int start) {
  if (start == arr.length) {
    print(arr);
    return;
  }
  for (int i = start; i < arr.length; i++) {
    swap(arr, start, i);
    permute(arr, start + 1);
    swap(arr, start, i);
  }
}

This code generates all permutations of the array by swapping elements starting from index 'start' and recursively permuting the rest.

Execution Table

Step	Operation	Indices Swapped	Array State	Action
1	Start permute at index 0	-	[1, 2, 3]	Begin permutation
2	Swap indices 0 and 0	(0,0)	[1, 2, 3]	Swap element with itself
3	Recurse permute at index 1	-	[1, 2, 3]	Permute subarray from index 1
4	Swap indices 1 and 1	(1,1)	[1, 2, 3]	Swap element with itself
5	Recurse permute at index 2	-	[1, 2, 3]	Permute subarray from index 2
6	Swap indices 2 and 2	(2,2)	[1, 2, 3]	Swap element with itself
7	Recurse permute at index 3	-	[1, 2, 3]	Reached end, print permutation
8	Backtrack swap indices 2 and 2	(2,2)	[1, 2, 3]	Restore array
9	Backtrack swap indices 1 and 1	(1,1)	[1, 2, 3]	Restore array
10	Swap indices 1 and 2	(1,2)	[1, 3, 2]	Swap to try new element at index 1
11	Recurse permute at index 2	-	[1, 3, 2]	Permute subarray from index 2
12	Swap indices 2 and 2	(2,2)	[1, 3, 2]	Swap element with itself
13	Recurse permute at index 3	-	[1, 3, 2]	Reached end, print permutation
14	Backtrack swap indices 2 and 2	(2,2)	[1, 3, 2]	Restore array
15	Backtrack swap indices 1 and 2	(1,2)	[1, 2, 3]	Restore array
16	Backtrack swap indices 0 and 0	(0,0)	[1, 2, 3]	Restore array
17	Swap indices 0 and 1	(0,1)	[2, 1, 3]	Swap to try new element at index 0
18	Recurse permute at index 1	-	[2, 1, 3]	Permute subarray from index 1
19	Swap indices 1 and 1	(1,1)	[2, 1, 3]	Swap element with itself
20	Recurse permute at index 2	-	[2, 1, 3]	Permute subarray from index 2
21	Swap indices 2 and 2	(2,2)	[2, 1, 3]	Swap element with itself
22	Recurse permute at index 3	-	[2, 1, 3]	Reached end, print permutation
23	Backtrack swap indices 2 and 2	(2,2)	[2, 1, 3]	Restore array
24	Backtrack swap indices 1 and 1	(1,1)	[2, 1, 3]	Restore array
25	Swap indices 1 and 2	(1,2)	[2, 3, 1]	Swap to try new element at index 1
26	Recurse permute at index 2	-	[2, 3, 1]	Permute subarray from index 2
27	Swap indices 2 and 2	(2,2)	[2, 3, 1]	Swap element with itself
28	Recurse permute at index 3	-	[2, 3, 1]	Reached end, print permutation
29	Backtrack swap indices 2 and 2	(2,2)	[2, 3, 1]	Restore array
30	Backtrack swap indices 1 and 2	(1,2)	[2, 1, 3]	Restore array
31	Backtrack swap indices 0 and 1	(0,1)	[1, 2, 3]	Restore array
32	Swap indices 0 and 2	(0,2)	[3, 2, 1]	Swap to try new element at index 0
33	Recurse permute at index 1	-	[3, 2, 1]	Permute subarray from index 1
34	Swap indices 1 and 1	(1,1)	[3, 2, 1]	Swap element with itself
35	Recurse permute at index 2	-	[3, 2, 1]	Permute subarray from index 2
36	Swap indices 2 and 2	(2,2)	[3, 2, 1]	Swap element with itself
37	Recurse permute at index 3	-	[3, 2, 1]	Reached end, print permutation
38	Backtrack swap indices 2 and 2	(2,2)	[3, 2, 1]	Restore array
39	Backtrack swap indices 1 and 1	(1,1)	[3, 2, 1]	Restore array
40	Swap indices 1 and 2	(1,2)	[3, 1, 2]	Swap to try new element at index 1
41	Recurse permute at index 2	-	[3, 1, 2]	Permute subarray from index 2
42	Swap indices 2 and 2	(2,2)	[3, 1, 2]	Swap element with itself
43	Recurse permute at index 3	-	[3, 1, 2]	Reached end, print permutation
44	Backtrack swap indices 2 and 2	(2,2)	[3, 1, 2]	Restore array
45	Backtrack swap indices 1 and 2	(1,2)	[3, 2, 1]	Restore array
46	Backtrack swap indices 0 and 2	(0,2)	[1, 2, 3]	Restore array
47	End	-	[1, 2, 3]	All permutations generated

💡 All indices swapped and recursed, permutations printed for each complete array

Variable Tracker

Variable	Start	After Step 2	After Step 10	After Step 17	After Step 32	Final
arr	[1, 2, 3]	[1, 2, 3]	[1, 3, 2]	[2, 1, 3]	[3, 2, 1]	[1, 2, 3]
start	0	1	1	1	1	3
i (loop index)	-	1	2	2	2	-

Key Moments - 3 Insights

Why do we swap elements back after recursion?

Swapping back restores the array to its original state before the next iteration, as shown in steps 8, 15, 30, 45, and 46 in the execution_table.

What happens when 'start' reaches the array length?

When 'start' equals the array length (step 7, 13, 22, 28, 37, 43), it means a full permutation is formed and printed.

Why do we swap the element with itself sometimes?

Swapping an element with itself (steps 2, 4, 6, etc.) is necessary to include the current element in the permutation without changing order.

Visual Quiz - 3 Questions

Look at the execution_table, what is the array state after step 10?

A [1, 3, 2]

B [1, 2, 3]

C [2, 1, 3]

D [3, 2, 1]

💡 Hint

Check the 'Array State' column at step 10 in the execution_table.

At which step does the first full permutation get printed?

A Step 13

B Step 7

C Step 22

D Step 37

💡 Hint

Look for 'Reached end, print permutation' in the Action column.

If we skip swapping back after recursion, what happens to the array state?

A Array remains unchanged

B Array becomes empty

C Array gets permanently modified, affecting next permutations

D Array size doubles

💡 Hint

Refer to key_moments about why swapping back is needed and steps showing backtracking swaps.

Concept Snapshot

Generate all permutations by swapping elements starting from 'start' index.
Recursively permute the rest of the array.
Print when 'start' reaches array length.
Swap back after recursion to restore original array.
This ensures all unique permutations are generated.

Full Transcript

This concept generates all permutations of an array by swapping elements starting from a given index. At each step, the element at the current index is swapped with each element from that index onward. Then, the function recursively permutes the remaining elements. When the start index reaches the array length, a complete permutation is printed. After each recursive call, the elements are swapped back to restore the original array state, allowing the next iteration to try a different element. This process continues until all permutations are generated and printed.

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